题目描述
思路解析
一句话答案：LeetCode 795 区间子数组个数用计数差分：定义 f(x)=最大值 ≤x 的子数组个数，答案=f(right)−f(left−1)，把『卡两头』拆成两次『只卡一头』。时间 O(n)、空间 O(1)。
所谓「最大值落在界内」的子数组，怎么数出来
给数组 nums 和两个界 left、right，要数出有多少个连续非空子数组，它的最大元素既 ≥left 又 ≤right，即最大值落在闭区间 [left, right]（含两端）里。题面 nums=[2,1,4,3]、left=2、right=3 时答案是 3：[2] 最大值 2、[2,1] 最大值 2、[3] 最大值 3 都卡在界内；含 4 的子数组最大值超界，单独一个 1 的又不够，都不算。
把每个子数组都框出来求最大值，慢在哪
顺着定义枚举每个子数组：固定左端，右端一路往后扩，扩时记住当前最大值，看它落不落在 [left, right]。子数组共 O(n²) 个，逐个查是 O(n²) 时间。n 上万时平方级就吃力，得想个一遍扫完的办法。
数「恰在界内」难，数「不超某条线」却容易
直接数「最大值恰好在 [left, right]」两头都卡着，不好下手。换个角度：定义 f(x)= 最大值 ≤x 的子数组个数，只卡上界，而「所有元素都 ≤x」的子数组好数得多。最大值 ≤right 的子数组共 f(right) 个，其中最大值还 ＜left（即 ≤left−1）的那批共 f(left−1) 个，是前者的子集。拿 f(right) 减掉 f(left−1)，剩的就是最大值 ≤right 又 ≥left 的，落在 [left, right] 的那些。答案 = f(right) − f(left−1)。
只卡一个上界，f(x) 一遍扫描就数得出
f(x) 能一遍线性扫出来。扫数组时维护一个 t，表示「以当前元素结尾、且这一段没有元素超过 x 的子数组个数」。碰到 v ≤x，它接在合法段后、也能自己单独成段，t 加一——以它结尾，每往右延一个合法元素就多一个左端点，加一而非翻倍；碰到 v ＞x，它像一堵墙，以它结尾的合法段一个没有，t 归零。每步把 t 累进 cnt，扫完就是 f(x)。一次遍历、几个计数器。
[2,1,4,3] 上，f(3) 与 f(1) 分别怎么算
right=3，先算 f(3)。v=2 ≤3，t=1，cnt=1；v=1 ≤3，t=2，cnt=3；v=4 ＞3，t 归零，cnt 仍是 3；v=3 ≤3，t=1，cnt=4。得 f(3)=4。再算 f(left−1)=f(1)。v=2 ＞1，t=0，cnt=0；v=1 ≤1，t=1，cnt=1；v=4 ＞1，t=0，cnt=1；v=3 ＞1，t=0，cnt=1。得 f(1)=1。答案 f(3) − f(1) = 4 − 1 = 3。
差分下界写成 f(left)，等于 left 的那些就被误删
两次 f(x) 各扫一遍，合起来仍是 O(n) 时间、O(1) 空间。两处容易写坏：一是差分下界得是 f(left−1) 不是 f(left)，写成 f(left) 会把最大值恰好等于 left 的合法子数组也一并扣掉，答案偏小；二是墙必须清零，v ＞x 时忘了把 t 归零、让它继续加，跨过墙、含超界元素的子数组就被错数进来。边界上，全部元素超界或全部 ＜left 时，f(right) 与 f(left−1) 相减都是 0，只有出现界内元素才数得出来。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「在界内算距离、偏小延续、超界清零」，下面每一帧都在套它。
start 记最近一个超过 right 的下标，开局当作 −1（还没出现过墙）。dp 记「以当前元素结尾的合法子数组数」，ans 是累计答案。从第 0 个开始扫。
第 0 个是 2，2 ≤ 2 ≤ 3，正好落在界内。它自己就能当一段子数组的最大值。
从 start 右边（下标 0）一直到 0，每个起点配上 0 都是一个合法子数组，共 1 个。绿色高亮的就是这 1 个子数组的起点范围。
把 dp = 1 累进答案，ans 现在是 1。
第 1 个是 1，1 < left=2，比下界还小。它当不了最大值，但也不会把最大值顶出界。
1 偏小，把它接到之前那些合法子数组后面，最大值还在原来那个界内元素手里，数量不变，dp 仍是 1。
把 dp = 1 累进答案，ans 现在是 2。
第 2 个是 4，4 > right=3，太大了。任何包含它的子数组，最大值都会超过 right。
4 超界，像一堵墙把窗口斩断。以它结尾的合法子数组一个都没有，dp 清零；start 记到 2，之后的窗口只能从墙右边算起。
这一步给答案加 0，ans 仍是 2。继续往后看。
第 3 个是 3，2 ≤ 3 ≤ 3，正好落在界内。它自己就能当一段子数组的最大值。
从 start 右边（下标 3）一直到 3，每个起点配上 3 都是一个合法子数组，共 1 个。绿色高亮的就是这 1 个子数组的起点范围。
把 dp = 1 累进答案，ans 现在是 3。
第 4 个是 2，2 ≤ 2 ≤ 3，正好落在界内。它自己就能当一段子数组的最大值。
从 start 右边（下标 3）一直到 4，每个起点配上 4 都是一个合法子数组，共 2 个。绿色高亮的就是这 2 个子数组的起点范围。
把 dp = 2 累进答案，ans 现在是 5。
第 5 个是 5，5 > right=3，太大了。任何包含它的子数组，最大值都会超过 right。
5 超界，像一堵墙把窗口斩断。以它结尾的合法子数组一个都没有，dp 清零；start 记到 5，之后的窗口只能从墙右边算起。
这一步给答案加 0，ans 仍是 5。继续往后看。
第 6 个是 3，2 ≤ 3 ≤ 3，正好落在界内。它自己就能当一段子数组的最大值。
从 start 右边（下标 6）一直到 6，每个起点配上 6 都是一个合法子数组，共 1 个。绿色高亮的就是这 1 个子数组的起点范围。
把 dp = 1 累进答案，ans 现在是 6。
全程扫完，每一步以当前元素结尾的合法子数组数依次是 1、1、0、1、2、0、1，相加得 6。这就是最终答案 6，整趟只扫了一遍。
边界先想清：全超界为 0、全偏小也为 0，只有出现界内元素才开始计数。
两个高频追问，重点是「偏小为何延续」与「两种解法等价」。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int: def f(x): cnt = t = 0 for v in nums: t = 0 if v > x else t + 1 cnt += t return cnt return f(right) - f(left - 1)复杂度
- 时间：O(n)，参考代码用 f(right)−f(left−1)，对数组做两次线性扫描，总时间仍是 O(n)
- 空间：O(1)，只用几个变量计数，常数空间
易错点
面试追问把动画讲成自己的话
追问为什么偏小（< left）的元素 dp 不清零，而是延续上一个值？
追问参考代码的 f(right) − f(left−1) 和动画的一遍三情况法是一回事吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
数组中的最长山脉
LeetCode 845 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题