题目描述
思路解析动画文字版
记住这套「在界内算距离、偏小延续、超界清零」，下面每一帧都在套它。
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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题