题目描述

给定一个元素都是正整数的数组 A，正整数 L 以及 R (L <= R)。

求连续、非空且其中最大元素满足大于等于 L 小于等于 R 的子数组个数。

样例

输入：
A = [2, 1, 4, 3]
L = 2
R = 3
输出：3
解释：满足条件的子数组：[2], [2, 1], [3]。

提示

• L、R 和 A[i] 都是整数，范围在 [0, 10^9]。
• 数组 A 的长度范围在 [1, 50000]。

算法1

(单调栈) $O(n)$

1. 我们独立考虑每个数字作为区间最大值时的情况。
2. 对于每一个数字 A[i]，考虑左边第一个大于等于它的位置 l（不存在则 l = -1），和右边第一个大于它的位置 r（不存在则 r = n）。
3. 如果 A[i] 在 [L, R] 限定的区间内，则根据乘法原理 ans += (r - i) * (i - l)。
4. 步骤 2 可以通过单调栈实现，维护一个不严格单调递减的栈。如果当前元素严格比栈顶元素大，则栈顶元素出栈，出栈过程中，r = i，l 就是栈顶元素出栈后的新的栈顶元素。

时间复杂度

• 每个元素仅入栈一次，出栈一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的栈空间，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
        const int MAX = 1000000010;

        A.push_back(MAX);
        int n = A.size();
        stack<int> st;
        int ans = 0;

        for (int i = 0; i < n; i++) {
            while (!st.empty() && A[st.top()] < A[i]) {
                int top = st.top();
                st.pop();
                if (L <= A[top] && A[top] <= R) {
                    if (!st.empty()) {
                        ans += (i - top) * (top - st.top());
                    } else {
                        ans += (i - top) * (top + 1);
                    }
                }
            }
            st.push(i);
        }

        return ans;
    }
};

算法2

(贪心) $O(n)$

1. 考虑以每个 i 为右端点的区间，我们期望找到一个尽可能小的 l (<= i) 和一个尽可能大的 r (<= i)，然后区间集 [l, i], [l + 1, i], ..., [r, i] 是满足条件的区间。
2. 如果在遍历过程中，发现了某个元素 A[i] > R，则我们就需要调整 l = i + 1，因为在 i 及之后位置作为右端点的区间，一定不能包含 i 这个位置。
3. 如果 A[i] <= R，我们接着判断是不是 A[i] >= L。如果成立，则更新 r = i，因为此时 A[l], A[l + 1], ..., A[r] 的最大值不会低于 L。
4. 此时我们确定了 l 和 r，如果 l <= r，则区间 [l, i], [l + 1, i], ..., [r, i] 都是满足条件的区间，区间个数共 r - l + 1 个。

时间复杂度

• 仅遍历数组一次，故时间复杂度为 $O(n)$。

空间复杂度

• 没有额外的数组，空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
        int n = A.size();
        int ans = 0, l = 0, r = -1;

        for (int i = 0; i < n; i++) {
            if (A[i] > R) {
                l = i + 1;
            } else {
                if (A[i] >= L) {
                    r = i;
                }
                ans += max(0, r - l + 1);
            }
        }

        return ans;
    }
};