LeetCode 581中等数组 · 双向扫描
最短无序连续子数组 图解题解
双向各扫一遍，找出所有乱队的元素，O(n) 时间 O(1) 空间确定最短乱序区间。
从左向右扫，手里攥着走过的最大值；谁比它小，谁就「乱了队」，右边界推到这里。再从右向左扫，手里攥着走过的最小值；谁比它大，谁也「乱了队」，左边界压到这里。两遍扫描确定的左右边界，就是必须重排的那一段。
这道题到底在问什么
给你一个整数数组 nums。只对其中某一段连续子数组升序排序，就能让整个数组变成升序。返回这样的子数组里最短的长度。
- 输入
- nums = [2,6,4,8,10,9,15]
- 输出
- 5
- 解释
- 只需排序中间这段 [6,4,8,10,9]，整个数组就有序了。
- 输入
- nums = [1,2,3,4]
- 输出
- 0
先想最直接的笨办法
笨办法：把数组拷一份排好序，再从两头找第一个对不上的位置，中间就是答案。好写，但排序要 O(n log n) 时间、还多花一份 O(n) 空间。（动画第 3 步）
最优解：一步一步想明白
- 3笨办法：把数组拷一份排好序，再从两头找第一个对不上的位置，中间就是答案。好写，但排序要 O(n log n) 时间、还多花一份 O(n) 空间。
- 4正向走一遍：谁比它左边见过的最大值还小，谁就乱了，右边界就推到这。反向再走一遍：谁比它右边见过的最小值还大，谁也乱了，左边界就压到这。
- 5max_seen=负无穷; right=-1从左往右扫。手里攥着目前见过的最大值 max_seen，谁敢比它小，谁就破坏了升序。
- 6x ≥ max_seen → 更新最大值第一个数 2，没有左边，直接当最大值。一切正常。
- 7x ≥ max_seen → 更新最大值6 比 2 大，继续升序，最大值刷成 6。
- 8x ＜ max_seen → right=i4 的左边出现过 6，比 4 大。说明 4 站错了位置，右边界先推到下标 2。
- 9x ≥ max_seen → 更新最大值8 比之前的 6 大，没破坏升序，最大值刷成 8。右边界按兵不动。
- 10x ≥ max_seen → 更新最大值10 又比 8 大，继续乖乖刷新最大值。它们都没破坏升序，右边界还停在 2。
- 11x ＜ max_seen → right=i9 的左边见过 10，比 9 大。9 也站错了，右边界再往后推到下标 5。最后的 15 最大，不影响。正向扫完，右边界定格在 5。
- 12min_seen=正无穷 → 最右当起始最小值现在从右往左扫，攥着右边见过的最小值 min_seen。谁比它还大，谁就该被排序段收进去。最右的 15 没有右邻，直接当起始最小值，记成 15。
- 13x ≤ min_seen → 更新最小值再往左到 9，它比 15 小，没破坏顺序，把最小值刷成 9。指针停在 9，面板也写 9，对齐。
- 14x ＞ min_seen → left=i10 的右边有个更小的 9。10 排在 9 前面是错的，所以 10 也得进排序段，左边界压到下标 4。
- 15x ≤ min_seen → 更新最小值往左走到 8、4，它们都不比右边最小值大，没问题。4 比 9 还小，把最小值刷成 4。
- 16x ＞ min_seen → left=i6 的右边有个更小的 4，6 排在前面是错的。左边界压到下标 1。再往左的 2 比 4 小，不动。反向扫完，左边界定格在 1。
- 17left=1, right=5 → 区间 [1,5]把两次扫描的结果叠在一起看：正向夹出右边界 5，反向夹出左边界 1。中间这段 [6,4,8,10,9] 就是最短无序段，长度 5-1+1 等于 5。
- 20一句话本质：用两个方向的单调极值，从两头把最短无序段夹出来。
- 22nums=[1,3,2,2,2]，正确答案 4如果只看“第一个下降位置”，会以为段在下标 2 就结束。但后面那串 2 仍然比左侧最大值 3 小，right 要一路推到下标 4。反向也把左边界压到 1。真实答案是排序 [3,2,2,2]，长度 4。
- 27把这题抽象成：正向维护一个单调极值、反向再维护一个，从两头夹出区间。接雨水、下一个排列都用得到这种双向扫描的思路。想巩固数组双向扫描，去 /leetcode-animation/ds?k=array 这个专题，或喊小欧帮你出几道同型题练手。
⚠️ 容易写错的地方
✗ 错：只找第一个下降的位置就停
✓ 对：用 max_seen / min_seen 一路扩展边界
无序段可能被更远处的小值或大值继续撑大，提前停会漏。
✗ 错：数组有序时返回 1
✓ 对：right 一直是 -1 就返回 0
已经升序的数组一段都不用排，长度是 0 不是 1。
✗ 错：比较时把等号也算进去
✓ 对：用严格的 ＜ 和 ＞，相等不更新边界
有重复值时，相等的数没破坏顺序，算进去会让区间偏长。
完整代码（Python / C++ / Java）
Python
class Solution:
def findUnsortedSubarray(self, nums):
n = len(nums)
right, max_seen = -1, float('-inf')
for i in range(n):
if nums[i] < max_seen:
right = i
else:
max_seen = nums[i]
left, min_seen = 0, float('inf')
for i in range(n - 1, -1, -1):
if nums[i] > min_seen:
left = i
else:
min_seen = nums[i]
return right - left + 1 if right != -1 else 0C++
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int n = nums.size(), right = -1;
int maxSeen = INT_MIN;
for (int i = 0; i < n; i++) {
if (nums[i] < maxSeen) right = i;
else maxSeen = nums[i];
}
int left = 0, minSeen = INT_MAX;
for (int i = n - 1; i >= 0; i--) {
if (nums[i] > minSeen) left = i;
else minSeen = nums[i];
}
return right == -1 ? 0 : right - left + 1;
}
};Java
class Solution {
public int findUnsortedSubarray(int[] nums) {
int n = nums.length, right = -1;
int maxSeen = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
if (nums[i] < maxSeen) right = i;
else maxSeen = nums[i];
}
int left = 0, minSeen = Integer.MAX_VALUE;
for (int i = n - 1; i >= 0; i--) {
if (nums[i] > minSeen) left = i;
else minSeen = nums[i];
}
return right == -1 ? 0 : right - left + 1;
}
}套路模板：双向扫描定区间（挖空骨架）
# 通法：正向定右边界，反向定左边界
def two_pass_bound(nums):
n = len(nums)
right, best = -1, float('-inf') # 正向极值
for i in range(n):
if 破坏单调(nums[i], best): # ← 填本题条件
right = i
else:
best = 更新极值(best, nums[i])
left, best2 = 0, float('inf') # 反向极值
for i in range(n - 1, -1, -1):
if 破坏单调2(nums[i], best2): # ← 反向条件
left = i
else:
best2 = 更新极值2(best2, nums[i])
return right - left + 1 if right != -1 else 0// 通法：正向定右边界，反向定左边界
int twoPassBound(vector<int>& nums) {
int n = nums.size(), right = -1, best = INT_MIN;
for (int i = 0; i < n; i++) {
if (/* 破坏单调: nums[i] < best */) right = i;
else best = max(best, nums[i]);
}
int left = 0, best2 = INT_MAX;
for (int i = n - 1; i >= 0; i--) {
if (/* 反向条件: nums[i] > best2 */) left = i;
else best2 = min(best2, nums[i]);
}
return right == -1 ? 0 : right - left + 1;
}// 通法：正向定右边界，反向定左边界
int twoPassBound(int[] nums) {
int n = nums.length, right = -1, best = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
if (/* 破坏单调: nums[i] < best */) right = i;
else best = Math.max(best, nums[i]);
}
int left = 0, best2 = Integer.MAX_VALUE;
for (int i = n - 1; i >= 0; i--) {
if (/* 反向条件: nums[i] > best2 */) left = i;
else best2 = Math.min(best2, nums[i]);
}
return right == -1 ? 0 : right - left + 1;
}复杂度
时间复杂度
O(n)
正向、反向各扫一遍，2n 次比较。
空间复杂度
O(1)
只存 max_seen、min_seen、left、right 四个变量。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最短无序连续子数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
右边界 right 怎么确定？+
从左到右维护 max_seen。一旦 nums[i] ＜ max_seen，说明 i 处的数被左边更大的数压着，必须进排序段，right 更新到 i。
左边界 left 怎么确定？+
从右到左维护 min_seen。一旦 nums[i] ＞ min_seen，说明 i 处的数比右边更小的数还大，也得进排序段，left 更新到 i。
为什么是 O(1) 空间，能不能再省时间？+
只用了四个标量变量，没有额外数组，所以 O(1) 空间。时间已经是 O(n)，两遍扫描是下界，无法再降。
数组本身就有序怎么办？+
正向扫一路没触发 nums[i] ＜ max_seen，right 始终是 -1，直接返回 0，表示无需排序。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。