LeetCode 795. 区间子数组个数

2024-05-10 HGNULB 约 10 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 795. 区间子数组个数

题意分析

给一个整数数组 nums 和两个整数 left、right，要求统计有多少个连续子数组，它的最大值落在闭区间 $[left, right]$ 内。子数组必须非空且连续，位置不同即视为不同的子数组，即使元素内容完全一样。

题面的关键信号是「最大值恰好落在一个区间内」。这类「统计满足某个双边约束的对象个数」的问题，双边约束本身很难直接维护——因为要同时盯住「不能太小」和「不能太大」两个方向，而这两个方向对滑动窗口的收缩规则要求是相反的。相比之下，单边约束「最大值不超过某个上界」极其好处理：它等价于「子数组内所有元素都不超过该上界」，是一个可以逐元素判定的性质。

第二个信号来自「最大值」这个聚合函数的单调性：往子数组里加元素，最大值只增不减。所以「最大值 $\le bound$」等价于「每个元素都 $\le bound$」，这让判定从「求一段区间的最大值」退化成「检查单个元素」，是整道题得以线性化的根基。注意这个性质对「最小值」「和」「乘积（含负数时）」并不都成立，不能无脑套用。

约束方面：数组长度不超过 $10^5$，元素值和 left、right 都在 $0$ 到 $10^9$ 之间，且保证 $left \le right$。$10^5$ 的规模要求 $O(n)$ 或 $O(n \log n)$，排除了 $O(n^2)$ 的枚举所有子数组。答案最坏是 $\frac{n(n+1)}{2} \approx 5 \times 10^9$，超出 int 范围——不过本题的官方约束保证答案在 int 内，所以用 int 累加是安全的，但这一点值得在面试时主动确认。

边界上要覆盖：所有元素都大于 right（答案为 $0$）；所有元素都在区间内（答案是子数组总数 $\frac{n(n+1)}{2}$）；left = 0（此时 left - 1 = -1，作为上界会让所有非负元素都不满足，count(-1) 恰好为 $0$）；数组中有连续多段合法区域被大元素隔开。

解法：区间计数转化

核心思路

先看暴力：枚举左右端点共 $O(n^2)$ 对，每对再求一次最大值。就算用「固定左端点向右扩展并顺带维护最大值」把求最大值降到均摊 $O(1)$，总复杂度仍是 $O(n^2)$，在 $10^5$ 下约 $10^{10}$ 次操作，超时。

瓶颈在于双边约束「$left \le \max \le right$」难以增量维护。想用滑动窗口的话，「$\max \le right$」要求窗口不能太大（遇到大元素要收缩），而「$\max \ge left$」要求窗口不能太小（遇不到足够大的元素要扩张），两个方向互相打架，窗口的移动规则无法统一。

关键观察是一个容斥转化：记 $f(bound)$ 为「最大值 $\le bound$ 的子数组个数」，那么答案就是 $f(right) - f(left - 1)$。因为「最大值 $\le right$」的子数组集合，减去「最大值 $\le left - 1$」的那部分，剩下的恰好是「最大值 $\ge left$ 且 $\le right$」的那些。后者是前者的子集（因为 $left - 1 < right$），所以直接相减不会出现负数或遗漏。这一步把一个双边问题拆成了两个单边问题，是本题唯一的技巧。

接下来只需高效计算 $f(bound)$。由于「最大值 $\le bound$」等价于「每个元素都 $\le bound$」，把数组中 $> bound$ 的元素看作「隔板」，数组就被切成若干段极大的合法区间，每段内部任取一个连续子数组都合法，段与段之间不能跨越。一段长度为 $L$ 的区间贡献 $\frac{L(L+1)}{2}$ 个子数组。

但更适合白板书写的是按右端点累加的写法：定义 cur 表示「以当前位置为右端点、且全部元素都 $\le bound$ 的子数组个数」。扫描时若当前元素 $\le bound$，则以它结尾的合法子数组可以由「以前一个位置结尾的每个合法子数组各接上当前元素」再加上「当前元素单独成段」得到，故 cur++；若当前元素 $> bound$，则任何以它结尾的子数组都含有这个超标元素，cur = 0。每一步把 cur 累加进 total。

于是维护的不变量是：扫描到下标 i 时，cur 恒等于「右端点为 i 且所有元素都 $\le bound$ 的子数组个数」，total 恒等于「右端点在 $[0, i]$ 范围内的全部合法子数组个数」。因为每个子数组有唯一的右端点，按右端点分类累加既不重也不漏，扫描结束时 total 就是 $f(bound)$。

这个写法的好处是不需要显式找段的起止位置，也不需要 $\frac{L(L+1)}{2}$ 这样的公式，只有一个 if 和两句累加，白板上三十秒能写完，且天然处理了「隔板在开头/结尾/连续出现」的各种情形。

解题步骤

主函数直接返回 count(nums, right) - count(nums, left - 1)。理由：这是容斥的直接落地；left - 1 作为上界表示「严格小于 left」，减掉它就把最大值过小的那些子数组排除掉了。

写辅助函数 count(nums, bound)，用 cur 和 total 两个变量，都初始化为 $0$。理由：把单边计数抽成独立函数，主函数才能复用两次；两个变量的初值对应「还没开始扫描，右端点为空」的状态。

单趟遍历数组，对每个元素判断 num <= bound：成立则 cur++，否则 cur = 0。理由：cur 的语义是「以当前位置结尾的合法子数组个数」。元素合法时，前一个位置的每个合法子数组延长一位仍合法，再加上「当前元素自己」这一个新的，恰好是 cur + 1；元素非法时，任何包含它的子数组都不合法，必须彻底清零而不是减一。

每轮把 cur 加进 total。理由：按右端点分类求和，每个合法子数组恰好在它自己的右端点处被计入一次，保证不重不漏。

返回 total。理由：扫描完成后不变量覆盖全数组，total 即为 $f(bound)$。

注意用 <= 而不是 < 做元素判定。理由：$f$ 的定义是「最大值不超过 bound」，闭区间；写成 < 会把等于 bound 的元素当成隔板，导致 $f(right)$ 少算而 $f(left-1)$ 也少算，两处误差不对称，最终答案错误。

以 nums = [2, 1, 4, 3]、left = 2、right = 3 走一遍。先算 count(nums, 3)：元素 $2 \le 3$，cur = 1，total = 1；元素 $1 \le 3$，cur = 2，total = 3；元素 $4 > 3$，cur = 0，total = 3；元素 $3 \le 3$，cur = 1，total = 4。所以 $f(3) = 4$，对应 [2]、[1]、[2,1]、[3]。再算 count(nums, 1)（即 left - 1 = 1）：元素 $2 > 1$，cur = 0，total = 0；元素 $1 \le 1$，cur = 1，total = 1；元素 $4 > 1$，cur = 0；元素 $3 > 1$，cur = 0，total = 1。所以 $f(1) = 1$，对应 [1]。答案 $4 - 1 = 3$，即 [2]、[2,1]、[3] 三个子数组的最大值落在 $[2,3]$ 内——[1] 因为最大值 $1 < 2$ 被减掉了，正是容斥要排除的那一部分。

代码实现

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

    private int count(int[] nums, int bound) {
        int cur = 0;
        int 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 countBound(nums, right) - countBound(nums, left-1)
}

func countBound(nums []int, bound int) int {
    cur := 0
    total := 0

    for _, num := range nums {
        if num <= bound {
            cur++
        } else {
            cur = 0
        }
        total += cur
    }

    return total
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是数组长度。count 是一趟线性扫描，每个元素只做一次比较和两次加法；主函数调用它两次，常数是 $2$，仍然是 $O(n)$。相比 $O(n^2)$ 的枚举，容斥转化让每个位置只被访问常数次。

空间复杂度：$O(1)$。只用了 cur 和 total 两个整型变量，不开辅助数组、不用栈也不做递归；输入数组是只读的，没有任何拷贝或预处理表。

关键点总结

「统计满足双边约束的对象个数」几乎都可以用容斥拆成两个单边问题：$f(\le R) - f(\le L-1)$。这一招在「和恰好为 K」「不同元素恰好 K 个」「乘积在区间内」等题上完全通用，是子数组计数最重要的模板之一。判断能否用的前提是两个集合有包含关系，本题因 $left - 1 < right$ 而天然成立。

「最大值 $\le bound$」等价于「所有元素 $\le bound$」，这是最大值单调性带来的红利，把区间聚合判定降成了逐元素判定。遇到最小值就反过来（$\ge bound$），遇到和或乘积则不成立，必须换用前缀和或双指针。

按右端点分类累加是子数组计数的通用骨架：维护「以当前位置结尾的合法子数组数」，逐位累加。它比「找出所有极大合法段再套 $\frac{L(L+1)}{2}$」更短、更少边界，而且能自然扩展到需要维护额外状态的变体。

隔板元素要把计数清零而不是递减。这体现的是「任何跨越隔板的子数组都非法」，是段与段之间不可合并的直接编码。

面试视角：字节考这题的期望是看你能否在两分钟内说出「双边转两次单边」。理想的作答节奏是：先说暴力 $O(n^2)$ 及其瓶颈「双边约束无法用滑动窗口维护」，再给出容斥式并解释为什么可以相减，最后写十行的 count。如果面试官追问「不用容斥能不能做」，可以补充另一种 $O(n)$ 解法：对每个位置维护「上一个大于 right 的位置」和「上一个落在 $[left, right]$ 内的位置」，两者之差就是以当前位置结尾的合法子数组数——这个写法只扫一遍，但边界更绕，用来展示储备正合适。

易错点总结

错误写法：写成 count(nums, right) - count(nums, left) → 用例 nums = [2, 1, 4, 3]，left = 2，right = 3 → count(nums, 2) 会把最大值恰好等于 $2$ 的子数组也减掉，答案变成 $4 - 3 = 1$，正确答案是 $3$；减去的必须是「严格小于 left」即上界 left - 1。

错误写法：元素判定用 num < bound 而不是 <= → 用例 nums = [3]，left = 3，right = 3 → count(nums, 3) 算成 $0$，答案是 $0 - 0 = 0$，正确答案是 $1$。

错误写法：遇到超标元素时写 cur-- 或 cur = cur > 0 ? cur - 1 : 0 → 用例 nums = [1, 5, 1]，bound = 1 → 第二个元素后 cur 只从 $1$ 降到 $0$ 看似没错，但 nums = [1, 1, 5, 1] 时 cur 从 $2$ 降到 $1$，第三个 $1$ 会让 cur 变 $2$，把跨越隔板的 [1(第二个), 5, 1] 计入，total 偏大。

错误写法：把 total += cur 写在 if 分支内部，超标时不累加也不清零 → 用例 nums = [1, 5, 1]，bound = 1 → cur 保持为 $1$ 没被清零，第三个元素时 cur 变 $2$，多算了一个跨隔板的子数组。

错误写法：left = 0 时没意识到 left - 1 = -1 是合法上界，额外加了 if (left == 0) return count(nums, right) 之外还把 left - 1 钳到 $0$ → 用例 nums = [0, 1]，left = 0，right = 1 → 钳到 $0$ 后会把最大值为 $0$ 的子数组 [0] 减掉，答案变成 $2$，正确答案是 $3$。

错误写法：用滑动窗口同时维护双边约束，收缩条件写成「窗口最大值 $> right$ 就左移」 → 用例 nums = [2, 1, 4, 3]，left = 2，right = 3 → 窗口能保证最大值不超过 $3$，但无法排除最大值小于 $2$ 的子数组，会把 [1] 也算进去，答案偏大。

错误写法：枚举所有子数组并对每个重新求最大值 → 用例长度 $10^5$ 的数组 → 约 $10^{10}$ 次操作，严重超时。

错误写法：把「段长为 L 贡献 $\frac{L(L+1)}{2}$」的公式写成 $\frac{L(L-1)}{2}$ 或 $L^2$ → 用例一段长度为 $2$ 的合法区间 → 正确贡献是 $3$（两个单元素加一个双元素），前者算成 $1$、后者算成 $4$，都不对。

错误写法：total 用 int 但在中间步骤先算出 $\frac{n(n+1)}{2}$ 再取模或转换 → 用例长度 $10^5$ 且全部元素合法的数组 → 中间值约 $5 \times 10^9$ 溢出；本题官方约束保证最终答案在 int 内，但若自行改写成公式法就要用 long 承接中间量。

错误写法：count 函数把 cur 声明在函数外或做成成员变量，两次调用之间不重置 → 用例任意输入 → 第二次调用 count(nums, left - 1) 时 cur 带着上一次的残值起步，结果偏大，相减后可能出现负数。

相似题目

题目	难度	考察点
992. K 个不同整数的子数组	困难	同样用「恰好 K = 至多 K 减至多 K-1」的容斥，但单边问题要靠滑动窗口而非计数
1248. 统计「优美子数组」	中等	把奇数个数作为约束，可用同一套容斥，也可用前缀和加哈希表，适合对照两种思路
713. 乘积小于 K 的子数组	中等	单边约束但聚合函数是乘积，不能逐元素判定，必须用滑动窗口维护
930. 和相同的二元子数组	中等	同为「恰好等于」型计数，主流解法是前缀和加哈希，也可用至多相减
907. 子数组的最小值之和	中等	从「统计个数」升级为「按最小值加权求和」，需要单调栈找每个元素的辖域