单调栈 加值太难想到怎么加。

这道题我刚开始想的是既然是subarray，那么以被stack pop出来的值为head最大也只能到当前(因为当前 < 被pop值) 所以结果pop值和当前值的距离。然后最后栈不是空的话再算一遍，最后结果 + 1 （加自己)

补充: 中途因为忘了自己本身已经加进去了，改来改去没改对，去看了题解发现直接加stack size也是对的，这种方式是记有哪些subarray而非我原来记从哪里开始可以多少种。

Intuition

Let nums[j] be the leftmost, see how far it can be. If some idx i with value nums[i] smaller than nums[j], then we know there exists i - j subarrays can start from j.

Approach

Use monotonic stack to store value, here we take increasing.

Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Code

class Solution {
public:

    int validSubarrays(vector<int>& nums) {
        int res = 0, n = nums.size();
        stack<int> st;
        for (int i = 0; i < n; i++){
            while(st.size() && nums[st.top()] > nums[i]){
                // top of stack is j
                auto curr = st.top(); st.pop();
                res += i - curr; // not include i
            }
            st.push(i);
        }
        auto last = st.top(); st.pop();
        while(st.size() && nums[st.top()] <= nums[last]){
            auto curr = st.top(); st.pop();
            res += last - curr + 1; // include last
        }
        return res + 1; // include [last] self
    }
};