202503141656 795 区间子数组个数

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

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

示例 1：

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

示例 2：

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

提示：

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

题解

DP 动态规划

给定数组 nums 及区间 [left, right]，要求统计连续子数组中其最大值落在区间内的子数组个数。直观暴力的思路是枚举所有子数组，然后判断最大值，但时间复杂度为 O(n²) 或更高，不适合 n 较大的情况。

状态定义： $dp[i]$ 表示以 $i$ 结尾的、满足 子数组最大值在 [left, right] 内 的子数组数量。 答案： $\text{ans}={\sum }_{i=0}^{n-1}dp[i]$

状态转移分析

在遍历过程中，我们需要注意三种情况（设上一次遇到不合法（即 > right）的位置为 j）：

1. $nums[i]>right$
   • 当前元素超出上界，任何以其结尾的子数组都必定非法。
   • 此时：$dp[i]=0$，并更新 $j=i$，表示将合法区间“断开”。
2. $left\le nums[i]\le right$
   • 当前元素本身合法，可以使包含它的子数组满足条件。
   • 以 i 为结尾的所有从 j+1 开始的子数组均合法，因此 $dp[i]=i-j$
3. $nums[i]<left$
   • 当前元素本身不满足条件，但如果前面已经出现过合法元素（即 $dp[i-1]$ 非 0），延伸这些子数组仍然合法。
   • 此时：$dp[i]=dp[i-1]$。

这种递推实际上构成了一种动态规划：

• 当 $nums[i]$ 在 $[left,right]$ 内时，“激活”了合法性，所有从上一次非法位置 $j$ 后开始的子数组都变合法。
• 当 $nums[i]<left$ 时，只能延续之前已经合法的子数组。
• 遇到 $nums[i]>right$ 时，必须断开连续区间。

在实际代码中，我们可以将 dp 数组压缩为一个变量（通常称为 temp），同时用变量 j 记录最后一个不合法的下标。

代码：完整 DP 框架

下面的代码中我们使用一个 dp 数组来保存每个位置的状态，最后将 dp 数组求和得到答案。

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        int n = nums.size();
        vector<int> dp(n, 0);
        int ans = 0;
        int last_invalid = -1; // 上一次出现 > right 的位置
        
        for (int i = 0; i < n; i++) {
            if (nums[i] > right) { 
                // 当前元素非法，断开连续区间
                last_invalid = i;
                dp[i] = 0;
            } else if (nums[i] >= left) {
                // 当前元素合法，激活连续子数组
                dp[i] = i - last_invalid;
            } else {
                // nums[i] < left，则只能延续前面的状态
                dp[i] = (i == 0 ? 0 : dp[i-1]);
            }
            ans += dp[i];
        }
        return ans;
    }
};

代码：状态压缩版

由于 dp[i] 仅依赖于前一个状态，我们可以用一个变量来保存当前状态，从而实现状态压缩。代码如下：

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        int ans = 0, temp = 0, last_invalid = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > right) {
                last_invalid = i;
                temp = 0; // 以当前位置结尾没有合法子数组
            } else if (nums[i] >= left) {
                temp = i - last_invalid; // 当前元素“激活”了合法性
            }
            // 当 nums[i] < left 时，temp 保持不变（延续之前合法子数组的数量）
            ans += temp;
        }
        return ans;
    }
};

这种写法相当于把完整 DP 中 $dp[i]$ 的状态直接压缩到了变量 temp 中。

单调栈 考虑最大值

对于数组中的每个元素，如果该元素满足 $left\le nums[i]\le right$，则它有可能作为某个子数组的最大值。
关键在于如何快速统计以 $nums[i]$ 为最大值的子数组个数。

如果我们能知道：

• 在 $nums[i]$ 左侧，离 $i$ 最近的且比 $nums[i]$ 大的元素的位置（记为 $l[i]$），
• 在 $nums[i]$ 右侧，离 $i$ 最近的且比 $nums[i]$ 大的元素的位置（记为 $r[i]$），
  那么，对于位置 $i$，其可以“支配”的子数组区间为：
• 子数组起点可以在区间 $(l[i]+1,i)$ 中任取，个数为 $(i-l[i])$；
• 子数组终点可以在区间 $(i,r[i]-1)$ 中任取，个数为 $(r[i]-i)$。

因此，以 $nums[i]$ 为最大值的子数组个数为：$(i-l[i])\ast (r[i]-i)$。

注意：
只有当 $nums[i]$ 落在 $[left,right]$ 内时，才能作为合法子数组的最大值：

• 如果 $nums[i]<left$，则不能单独激活合法性；
• 如果 $nums[i]>right$，则整个子数组不合法。