题目解析：对于每一个元素，右边第一个比它小的元素之前的元素构成的子数组都满足条件，也就是求右边第一个比它小的元素位置pos，将res += pos-i ;可以用单调栈来实现。遍历结束后，对于仍在栈中的元素,res += n - i ;时间复杂度为O(N） ， 空间复杂度为O(N);
class Solution {
public:
int validSubarrays(vector<int>& nums)
{
int res = 0 ;
stack<int> s ;
for(int i = 0 ; i < nums.size() ; i++)
{
while(!s.empty() && nums[i] < nums[s.top()])
{
res += i - s.top() ;
s.pop() ;
}
s.push(i) ;
}
while(!s.empty())
{
res += nums.size() - s.top() ;
s.pop() ;
}
return res ;
}
};
leetcode 1063. Number of Valid Subarrays
原文：https://www.cnblogs.com/mychen06/p/12592729.html