【Leetcode】1063. Number of Valid Subarrays

题目地址：

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

给定一个长$n$数组$A$，求满足这样条件的子数组个数：该子数组的左端点的值不大于其余数字。

设$A[i]$右边的第一个比其小的数是$A[j]$，那么以$A[i]$作为左端点的满足条件的子数组的个数即为$j-i$（如果不存在，则个数为$n-i$）。而求每个数右边第一个比其小的数的位置可以用单调栈来做。代码如下：

class Solution {
 public:
  int validSubarrays(vector<int>& A) {
    stack<int> stk;
    int res = 0;
    for (int i = 0; i < A.size(); i++) {
      while (stk.size() && A[stk.top()] > A[i]) {
        res += i - stk.top();
        stk.pop();
      }

      stk.push(i);
    }

    while (stk.size()) {
      res += A.size() - stk.top();
      stk.pop();
    }

    return res;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时空复杂度$O(n)$。