BinarySearch 0899 Number of Sublists With Small Left Value

Problem statement

https://binarysearch.com/problems/Number-of-Sublists-With-Small-Left-Value/

Solution

Equal to Leetcode 1063. Number of Valid Subarrays

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(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