[Leetcode] 3113. Find the Number of Subarrays Where Boundary Elements Are Maximum

https://leetcode.com/problems/find-the-number-of-subarrays-where-boundary-elements-are-maximum/description/

initial

no idea at all lol

so there is this concept of monotic decreasing stack, where in ur stack you have decreasing values stored like [69,2,1]. So the first left element in stack is the largest.

the logic we can use here is as we store values in this decreasing stack, if the current number is greater or equal to the largest number stored in stack, we pop all the values in stack that are lower than this number.

But if this number and the largest value stored in stack is the same, that is the valid case. In which case we add arr[idx] to our arr[i] where arr[i] stores number of valid cases ending at index i. arr[idx] idx is the index of the largest value stored in stack.

this is cuz we can extend the arr[idx] valid cases to the curernt arr[i]

sol

from collections import deque
class Solution:
    def numberOfSubarrays(self, nums: List[int]) -> int:
        stack = deque()
        arr = [1 for _ in range(len(nums))]
        for i,v in enumerate(nums):
            while stack and nums[i]>=nums[stack[0]]:
                idx = stack.popleft()
                if(nums[i]==nums[idx]):
                    arr[i]+=arr[idx]
            stack.appendleft(i)
        return sum(arr)

complexity

n time
n space