LeetCode 795. 区间子数组个数
题目描述
题意分析
统计连续、非空且最大值位于
[left, right]的子数组。限制的是整个子数组的最大值，所以其中可以包含小于left的元素；只要最大值达到left，又没有超过right即可。同时维护上下界不方便时，可以先统计最大值不超过某个上界的子数组，再减去最大值过小的部分。
解法：区间计数转化
核心思路
[!blue]
令
f(bound)表示最大值不超过bound的非空子数组数量。f(right)包含所有最大值不超过右界的子数组，其中不合法的恰好是最大值小于left的那些。元素都是整数，“小于left”等价于“不超过left - 1”，所以答案为f(right) - f(left - 1)。一个子数组的最大值不超过
bound，等价于它的每个元素都不超过bound。因此，任何超标元素都是不能跨越的分隔点。扫描到当前位置时，用cur保存以这里结尾、所有元素都合格的最长连续后缀长度。当前元素合格时，之前的合法后缀可以向右延长一格，令
cur++；当前元素超标时，不存在以它结尾的合法非空子数组，令cur = 0。若cur > 0，最长后缀中的每个位置都可以作为起点，恰好产生cur个以当前位置结尾的合法子数组，因此每一步将cur加入total。每个子数组都有唯一的右端点，且在该右端点处只有一个对应起点。按右端点累加就覆盖了全部合法子数组，不会重复。两次计数各自使用独立的局部状态，最后作差即可筛出所需最大值区间。
虽然题目保证最终答案在 32 位整数范围内，但
f(right)、f(left - 1)各自可能很大。长度为n的数组最多有n * (n + 1) / 2个子数组，n可达 $10^5$，所以辅助计数使用long或int64；先在宽整数中相减，再转换为返回类型。
解题步骤
- 分别按两个上界线性扫描。
- 合格时延长后缀，否则清零。
- 逐右端累加贡献，最后相减。
left == 0时，第二次计数的上界为-1；题目保证元素非负，因此这一项自然为零。left == right时，差值统计的正是最大值等于这个数的子数组。cur最多等于数组长度，可以继续使用普通整数。
代码实现
class Solution {
public int numSubarrayBoundedMax(int[] nums, int left, int right) {
// 先用宽整数做两个精确累计计数的差，再转换公开结果
return (int) (count(nums, right) - count(nums, left - 1));
}
private long count(int[] nums, int bound) {
int cur = 0;
// 辅助计数可能超过32位，使用宽整数保存
long total = 0;
for (int num : nums) {
if (num <= bound) {
cur++;
} else {
cur = 0;
}
// 当前合法后缀的每个起点贡献一个子数组
total += cur;
}
return total;
}
}
func numSubarrayBoundedMax(nums []int, left int, right int) int {
// 先用宽整数做两个精确累计计数的差，再转换公开结果
return int(countBound(nums, right) - countBound(nums, left-1))
}
func countBound(nums []int, bound int) int64 {
cur := 0
// 辅助计数可能超过32位，使用宽整数保存
var total int64
for _, num := range nums {
if num <= bound {
cur++
} else {
cur = 0
}
// 当前合法后缀的每个起点贡献一个子数组
total += int64(cur)
}
return total
}
复杂度分析
- 时间复杂度：$O(n)$，两次线性计数。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 左边界也包含在答案内，因此减去 left−1。
- 每个子数组只按自己的右端点计一次。
易错点总结
[!yellow]
- 减去 f(left)，会删除最大值恰为左边界的结果。
- 分隔点只减一而不清零，会计入跨过超标值的子数组。
- 两次调用未重置状态，会破坏计数相减的含义。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 2444. 统计定界子数组的数目 | 困难 | 同样按最近失效位置和命中边界统计以当前位置结尾的合法区间，原题同时固定最小值和最大值。 |
| 209. 长度最小的子数组 | 中等 | 同样统计或寻找满足区间条件的窗口，本题约束最大值，可通过两个单边界计数之差求解。 |