Number of Subarrays with Bounded Maximum LeetCode solution in Python

1
# Runtime: 1574 ms (Top 5.27%) | Memory: 22.4 MB (Top 17.30%)
2
class Solution:
3
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
4
        n = len(nums)
5
        stack = []
6
        next_greater = [n] * n
7
        prev_greater = [-1] * n
8
        for i in range(n):
9
            while len(stack) > 0 and nums[i] > nums[stack[-1]]:
10
                curr = stack.pop()
11
                next_greater[curr] = i
12
            if len(stack) > 0:
13
                prev_greater[i] = stack[-1]
14
            stack.append(i)
15
        res = 0
16
        for i in range(n):
17
            if left <= nums[i] <= right:
18
                l = prev_greater[i]
19
                r = next_greater[i]
20
                res += (i - l) * (r - i)
21
        return res