Problem statement

https://leetcode.com/problems/number-of-valid-subarrays/

Solution

What is actually asked in this problem: for every index $i$ we need to find the smallest $j > i$, such that nums[j] < nums[i]. Let us traverse our numbers and put them into stack (in fact we will put indexes), such that we always have non-decreasing order in our stack. For example if we have [1, 4, 2, 3, 5], then we have the following steps.

[1] [1, 4] [1, 2] [1, 2, 5] [1, 2, 3]

Note, that when we extract some element from stack, e.g we have [1, 4] and next element is 2, it means that we found answer for number 4, so we add it to final answer.

Complexity

Time and space complexity is $O(n)$.

Code

class Solution:
    def validSubarrays(self, nums):
        nums += [float('-inf')]
        res, stack, n = 0, [], len(nums)
        
        for i in range(n):
            while stack and nums[stack[-1]] > nums[i]:
                res += i - stack.pop()
            stack.append(i)
        return res