统计定界子数组的数目 图解题解
这道题到底在问什么
- 输入
- nums=[1,3,5,2,7,5], minK=1, maxK=5
- 输出
- 2
- 输入
- nums=[1,1,1,1], minK=1, maxK=1
- 输出
- 10
最优解：一步一步想明白
- 3记住「bad 截左界、lastMin/lastMax 给右界;每步加 max(0, min(lm,lx) − bad)」,下面每一格都在套它。
- 4这一行是数组。bad、lastMin、lastMax 一开始都是 −1(还没遇到)。右指针从左往右一格格扫,我们盯着这三个位置和 ans 怎么变。
- 5右指针到第 0 位,值 1,它正好是 minK。它能当 minK,把对应的最近位置更新到 0(绿色)。
- 6以第 0 位为右端时,minK 或 maxK 还没同时出现,凑不出合法左端,这一步贡献 0,ans 不变,仍是 0。
- 7右指针到第 1 位,值 3,它普通(在界内)。它在界内、但既不是 minK 也不是 maxK,三个位置都不变。
- 8以第 1 位为右端时,minK 或 maxK 还没同时出现,凑不出合法左端,这一步贡献 0,ans 不变,仍是 0。
- 9右指针到第 2 位,值 5,它正好是 maxK。它能当 maxK,把对应的最近位置更新到 2(绿色)。
- 10以第 2 位为右端,合法左端要在 bad=-1 右边、又不能晚于 min(lastMin,lastMax)=0,也就是下标 0 到 0 这 1 个起点,每个都框出一个合法子数组。答案加 1,累计 1。
- 11右指针到第 3 位,值 2,它普通(在界内)。它在界内、但既不是 minK 也不是 maxK,三个位置都不变。
- 12以第 3 位为右端,合法左端要在 bad=-1 右边、又不能晚于 min(lastMin,lastMax)=0,也就是下标 0 到 0 这 1 个起点,每个都框出一个合法子数组。答案加 1,累计 2。
- 13右指针到第 4 位,值 7,它越界。这是个越界数,合法子数组绝不能跨过它,把 bad 推到 4(红色)。
- 14以第 4 位为右端时,min(lastMin,lastMax)=0 没越过 bad=4,凑不出合法左端,这一步贡献 0,ans 不变,仍是 2。
- 15右指针到第 5 位,值 5,它正好是 maxK。它能当 maxK,把对应的最近位置更新到 5(绿色)。
- 16以第 5 位为右端时,min(lastMin,lastMax)=0 没越过 bad=4,凑不出合法左端,这一步贡献 0,ans 不变,仍是 2。
- 17右指针到第 6 位,值 1,它正好是 minK。它能当 minK,把对应的最近位置更新到 6(绿色)。
- 18以第 6 位为右端,合法左端要在 bad=4 右边、又不能晚于 min(lastMin,lastMax)=5,也就是下标 5 到 5 这 1 个起点,每个都框出一个合法子数组。答案加 1,累计 3。
- 19右指针到第 7 位,值 4,它普通(在界内)。它在界内、但既不是 minK 也不是 maxK,三个位置都不变。
- 20以第 7 位为右端,合法左端要在 bad=4 右边、又不能晚于 min(lastMin,lastMax)=5,也就是下标 5 到 5 这 1 个起点,每个都框出一个合法子数组。答案加 1,累计 4。
- 21右指针到第 8 位,值 5,它正好是 maxK。它能当 maxK,把对应的最近位置更新到 8(绿色)。
- 22以第 8 位为右端,合法左端要在 bad=4 右边、又不能晚于 min(lastMin,lastMax)=6,也就是下标 5 到 6 这 2 个起点,每个都框出一个合法子数组。答案加 2,累计 6。
- 23扫完全程,把每个右端点贡献的「max(0, min(lastMin,lastMax) − bad)」加起来,一共 6 个子数组的最小值正好是 1、最大值正好是 5。只用三个位置变量、一遍扫完,O(n)。
⚠️ 容易写错的地方
✗ 错：把它当普通滑动窗口左右收缩
✓ 对：三指针记最近位置、按右端点累加
合法性同时受「越界截断」和「必须含 minK、maxK」两个约束,普通单窗口表达不了
✗ 错：贡献写成 min(lm,lx) − bad
✓ 对：要套 max(0, …)
minK、maxK 还没同时出现、或最近的它们被 bad 截在左边时,差是负的,必须压成 0
✗ 错：minK==maxK 时漏处理
✓ 对：同一个数同时刷新 lastMin 和 lastMax
此时只要窗口里有一个 = minK(=maxK)且无越界即可,公式自然成立
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
bad = last_min = last_max = -1
ans = 0
for i, x in enumerate(nums):
if x < minK or x > maxK:
bad = i
if x == minK:
last_min = i
if x == maxK:
last_max = i
ans += max(0, min(last_min, last_max) - bad)
return ansC++
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
long long countSubarrays(vector<int>& nums, int minK, int maxK) {
long long ans = 0;
int bad = -1, lastMin = -1, lastMax = -1;
for (int i = 0; i < (int)nums.size(); ++i) {
if (nums[i] < minK || nums[i] > maxK) bad = i;
if (nums[i] == minK) lastMin = i;
if (nums[i] == maxK) lastMax = i;
ans += max(0, min(lastMin, lastMax) - bad);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public long countSubarrays(int[] nums, int minK, int maxK) {
long ans = 0;
int bad = -1, lastMin = -1, lastMax = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] < minK || nums[i] > maxK) bad = i;
if (nums[i] == minK) lastMin = i;
if (nums[i] == maxK) lastMax = i;
ans += Math.max(0, Math.min(lastMin, lastMax) - bad);
}
return ans;
}
}复杂度
时间
O(n)
一遍扫描,每个位置只看一次、三个下标各自只增不减
空间
O(1)
只用 bad、lastMin、lastMax、ans 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 统计定界子数组的数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么按「以每个 i 结尾」来数就不重不漏?+
任何一个连续子数组都有唯一的右端点。我们对每个 i 数出「以它结尾的合法子数组个数」,再把所有 i 的结果加起来,每个子数组恰好被它自己的右端点数到一次,所以不重不漏。
为什么三个位置都只记「最近」的一个,不用记历史?+
对固定右端 i 来说,左界只取决于「最近的越界位」(它把更早的合法区间废掉了)和「最近的 minK、maxK 位」(要含到它们,左端就不能比它们更晚)。更早的越界位、更早的 minK/maxK 都被最近的覆盖,记最近的就够了。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 统计定界子数组的数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。