Number of Valid Subarrays

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

The leftmost element of the subarray is not larger than other elements in the subarray.

这题我一开始用的暴力解法，O(N^2)

class Solution(object):
    def validSubarrays(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for i in range(len(nums)):
            curr = nums[i]
            j = i+1
            while j < len(nums) and nums[j] >= curr:
                j+=1
            res += j-i
        return res

看上去很直观，但是更优的解法是next greater element的用stack的O(N)解法

class Solution(object):
    def validSubarrays(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nextSmaller = [len(nums)] * len(nums)
        stack = []
        for i,v in enumerate(nums):
            while len(stack) != 0 and stack[-1][1] > v:
                nextSmaller[stack.pop()[0]] = i
            stack.append([i,v])
        return sum([v-i for i,v in enumerate(nextSmaller)])