leetcode *795. 区间子数组个数（2022.11.24）

【题目】*795. 区间子数组个数

2444. 统计定界子数组的数目

给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。
生成的测试用例保证结果符合 32-bit 整数范围。

示例 1：

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

示例 2：

输入：nums = [2,9,2,5,6], left = 2, right = 8
输出：7
1
2

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= left <= right <= 109
1
2
3

【解题思路1】

一个子数组的最大值范围在 [left,right] 表示子数组中不能含有大于 right 的元素，且至少含有一个处于 [left,right] 区间的元素。

我们可以将数组中的元素分为三类，并分别用 0, 1, 2 来表示：

• nums[i]< left，用 0 表示；
• left <= nums[i] <= right，用 1 表示；
• nums[i] > right，用 2 表示。
  那么本题可以转换为求解不包含 2，且至少包含一个 1 的子数组数目。所以，我们可以先求出只包含 0 或 1 的子区间数目，再减去只包括 0 的子区间数目。

设函数 count(nums,lower) 可以求出数组 nums中所有元素小于等于 lower 的子数组数目，那么题目所求就是 count(nums,right)−count(nums,left)。

关于 count(nums,lower) 的实现，我们用 i 遍历 nums[i]，cur 表示 i 左侧有多少个连续的元素小于等于 lower：

• 如果 nums[i]≤lower，令 cur=cur+1；
• 否则，令 cur=0。
  每次将 cur加到答案中，最终的和即为 count 函数返回值。

这边我只想到了遍历计数，得到一个满足条件区间的长度len，然后这个区间可以组成的子数组个数就是 (1+len)*len/2，也就是从1累加到n，没有想到可以在遍历的时候直接累加= =

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        return count(nums, right) - count(nums, left - 1);
    }

    // 求出数组 nums 中所有元素小于等于 lower 的子数组数目
    public int count(int[] nums, int lower) {
        int res = 0, cur = 0;
        for (int x : nums) {
            cur = x <= lower ? cur + 1 : 0;
            res += cur;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

【解题思路2】固定右端点

这就想不到了= =
我们遍历 i，并将右端点固定在 i，求解有多少合法的子区间。过程中需要维护两个变量：

last1，表示上一次 1 出现的位置，如果不存在则为 −1；
last2，表示上一次 2 出现的位置，如果不存在则为 −1。
如果 last1≠−1，那么子数组若以 i 为右端点，合法的左端点可以落在 (last2,last1]之间。这样的左端点共有 last1−last2个。

因此，我们遍历 i：
如果 left≤nums[i]≤right，令 last1=i否则如果 nums[i]>right，令 last2=i，last1=−1。
然后将 last1−last2 累加到答案中即可。最后的总和即为题目所求。

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int res = 0, last2 = -1, last1 = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= left && nums[i] <= right) {
                last1 = i;
            } else if (nums[i] > right) {
                last2 = i;
                last1 = -1;
            }
            if (last1 != -1) {
                res += last1 - last2;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17