# 1063. Number of Valid Subarrays
###### tags: `Leetcode` `Hard` `Monotonic Stack`
Link: https://leetcode.com/problems/number-of-valid-subarrays/
## 思路 $O(N)$ $O(N)$
找next smaller 所以是单调递增栈
ans每次加stack.size() 是因为栈里面的每个元素 都可以代表一个以它为leftmost元素 rightmost是当前值$nums[i]$的答案array

## Code

class Solution:
    def validSubarrays(self, nums: List[int]) -> int:
        stack = []
        ans = 0
        for num in nums:
            while stack and stack[-1]>num:
                stack.pop()
            stack.append(num)
            ans += len(stack)
        return ans

class Solution {
    public int validSubarrays(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int ans = 0;
        for(int i=0; i<nums.length; i++){
            while(!stack.isEmpty() && nums[stack.peek()]>nums[i]){
                stack.pop();
            }
            stack.push(i);
            ans += stack.size();
        }
        return ans;
    }
}