每日一题 —— LC. 795 区间子数组个数

795. 区间子数组个数

给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。

生成的测试用例保证结果符合 32-bit 整数范围。

提示

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9
• 0 <= left <= right <= 10^9

示例

输入：nums = [2,1,4,3], left = 2, right = 3
输出：3
解释：满足条件的三个子数组：[2], [2, 1], [3]
1
2
3

思路

数据范围为10^5，那么暴力枚举全部子数组一定是不可行的。

题目要求子数组的最大元素，必须在范围[left, right]内。

我们运用逆向思维，不先枚举子数组，再求最大值；而通过最大值，来求子数组。

也就是说，对于某个元素nums[i]，我们计算一下，以nums[i]作为最大值的子数组有多少个，若此时nums[i]的大小恰好在[left, right]范围内，则我们对子数组的数量进行累加。

---

关键一：逆向思维，通过最大值，来求子数组数量

---

那么对于某个元素nums[i]，我们如何求得以其作为最大值的子数组有多少个呢？很明显的，子数组中若要nums[i]最大，则左侧不能有比它大的，右侧也不能有比它大的。而子数组（不同于子序列）是连续的。

所以，我们只要求解一下i左侧第一个比nums[i]大的元素在什么位置，i右侧第一个比nums[i]大的元素在什么位置。求出这两个位置后，那么对于中间部分的所有元素，nums[i]就是最大值，我们就能非常容易的计算出以nums[i]为最大值的子数组的个数了。

对于求解某个数左侧第一个比其大，这样的问题，很明显的，应该用单调栈。

---

关键点二：单调栈

---

我们只需要用单调栈，通过两次遍历，求出每个数左侧第一个比其大的位置，右侧第一个比其大的位置。

然后最后再遍历一次，能够求出每个元素作为最大值的子数组的数量，对于那些满足条件的元素，进行子数组数量的累加即可。

// C++
class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        // 求每个数左边, 右边, 第一个大于大于这个数的数
        int n = nums.size();
        vector<int> leftBorder(n, -1);
        vector<int> rightBorder(n, n);
        stack<int> stk;
        for (int i = 0; i < n; i++) {
            while (stk.size() && nums[stk.top()] <= nums[i]) stk.pop();
            if (stk.size()) leftBorder[i] = stk.top();
            stk.push(i);
        }
        while (stk.size()) stk.pop();
        for (int i = n - 1; i >= 0; i--) {
            while (stk.size() && nums[stk.top()] <= nums[i]) stk.pop();
            if (stk.size()) rightBorder[i] = stk.top();
            stk.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            // 不在[left,right]范围内的直接跳过
            if (nums[i] < left || nums[i] > right) continue;
            int llen = i - leftBorder[i], rlen = rightBorder[i] - i;
            ans += llen * rlen; // 乘法原理
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

到这里还没结束，因为可能有相同元素的存在，所以上面的代码会重复统计某些子数组。所以我们还需要去重。

---

关键点三：去重

---

具体去重的方式，与 907. 子数组的最小值之和 这道题一样，我们只要在一侧求解大于等于，另一侧求解大于。就能完成去重。并且，可以通过一次遍历同时求出左右两侧的值。

// C++
class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        // 求每个数左边, 右边, 第一个大于大于这个数的数
        int n = nums.size();
        vector<int> leftBorder(n, -1);
        vector<int> rightBorder(n, n);
        stack<int> stk;
        for (int i = 0; i < n; i++) {
            while (stk.size() && nums[stk.top()] <= nums[i]) {
                rightBorder[stk.top()] = i;
                stk.pop();
            }
            if (stk.size()) leftBorder[i] = stk.top();
            stk.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] < left || nums[i] > right) continue;
            int llen = i - leftBorder[i], rlen = rightBorder[i] - i;
            ans += llen * rlen;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

本题也有另外时间复杂度更优秀的做法，参考官网题解。