给定一个整数数组 A,返回满足下面条件的 非空、连续 子数组的数目:
子数组中,最左侧的元素不大于其他元素。
示例 1:
输入:[1,4,2,5,3]
输出:11
解释:有 11 个有效子数组,分别是:[1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3] 。
示例 2:
输入:[3,2,1]
输出:3
解释:有 3 个有效子数组,分别是:[3],[2],[1] 。
示例 3:
输入:[2,2,2]
输出:6
解释:有 6 个有效子数组,分别为是:[2],[2],[2],[2,2],[2,2],[2,2,2] 。
提示:
1 <= A.length <= 50000
0 <= A[i] <= 100000
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/number-of-valid-subarrays 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
[s.top(),i-1]
的 都是满足的子数组class Solution {
public:
int validSubarrays(vector<int>& nums) {
stack<int> s;
nums.push_back(-1); // 保证最后全部清空栈
int count = 0;
for(int i = 0; i < nums.size(); ++i)
{
while(!s.empty() && nums[i] < nums[s.top()])
{
count += i-s.top();
s.pop();
}
s.push(i);
}
return count;
}
};
160 ms 43.8 MB