LeetCode-Go 实战解析：581. Shortest Unsorted Continuous Subarray 最短未排序连续子数组

LeetCode-Go 实战解析：581. Shortest Unsorted Continuous Subarray 最短未排序连续子数组

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文围绕 LeetCode 第 581 题「最短未排序连续子数组（Shortest Unsorted Continuous Subarray）」展开，结合 LeetCode-Go 仓库中的完整题解与测试用例，深入拆解"最短逆序区间"的判定原理与 O(n) 时间、O(1) 空间的线性扫描解法。读完本文，你将掌握如何仅凭一趟从左到右、一趟从右到左的扫描，确定逆序区间的最小元素与最大元素，再还原出区间左右边界并输出最短长度，同时理解边界值（minR / maxL）为何必须单独还原，以及该实现通过仓库单测验证的完整过程。

题目与题意

题目原文

给定一个整数数组nums，你需要找出一个连续子数组（continuous subarray）：只要将该子数组按升序排序，整个数组就会变为升序。请返回满足条件的最短子数组的长度。

题目位于 leetcode/0581.Shortest-Unsorted-Continuous-Subarray 目录，README 中给出了如下示例：

示例 1：

Input: nums = [2,6,4,8,10,9,15] Output: 5 Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

示例 2：

Input: nums = [1,2,3,4] Output: 0

示例 3：

Input: nums = [1] Output: 0

约束条件：

• 1 <= nums.length <= 10^4
• -10^5 <= nums[i] <= 10^5

题意解读

• 若整个数组本身已经升序，例如[1,2,3,4]，则无需排序任何子数组，答案为0。
• 若数组只有一个元素，例如[1]，同样天然有序，答案为0。
• 示例 1 中，中间一段[6,4,8,10,9]乱序，只要把这段排序为[4,6,8,9,10]，整个数组即变为[2,4,6,8,9,10,15]，因此最短长度为5。

注意：要求的是"最短"连续子数组，也就是要把"乱序贡献范围"压缩到最小，既不能漏掉任何一个破坏升序的位置，也不能把本已有序的区间多算进去。

解题思路：最短逆序区间的判定原理

核心观察：区间由最小元素定左界、最大元素定右界

README 的解题思路给出了最关键的推理：这个逆序区间一定由区间内的最小元素决定左边界，最大元素决定右边界。

直觉上可以这样理解：

• 一段乱序区间之所以"乱"，是因为区间内部存在下降（nums[i] > nums[i+1]之类）的相邻关系；
• 排序这段区间后，它内部的最小值会被放到区间最左端，最大值会被放到区间最右端；
• 因此，最短逆序区间的左边界取决于"第一个被区间内最小值"影响到的位置，右边界取决于"最后一个被区间内最大值"影响到的位置。

四步扫描策略（README 思路的完整展开）

README 中给出了一个清晰的 O(n) 思路，可以拆解为四个阶段：

1. 从左向右扫描，确定逆序区间内的最小元素min：找到第一个降序点（nums[i] < nums[i-1]）之后，持续记录后续元素中的最小值，记为minR。
2. 从右向左扫描，确定逆序区间内的最大元素max：找到第一个"右侧降序点"（nums[i] > nums[i+1]）之后，持续记录左侧元素中的最大值，记为maxL。
3. 还原左边界：从左往右找到第一个大于minR的元素位置，这才是逆序区间的真正左边界。
4. 还原右边界：从右往左找到第一个小于maxL的元素位置，这才是逆序区间的真正右边界。

为什么要"还原"边界？一个关键的反直觉点

README 特别强调了这一点：不能直接取第一次出现降序的位置作为边界。

以左边界为例：如果区间外（左侧）的某个元素比逆序区间内的最小元素minR还要小，说明它并不是左边界——因为这个小元素与minR组合在一起依然保持升序，并未破坏顺序。只有在左侧区间外找到第一个大于minR的元素，才说明"逆序从这里刚刚开始"，这才是最小逆序区间的左边界。

同理，右边界需要在右侧区间外找到第一个小于maxL的元素，说明逆序延伸到此处才结束。

例如[1, 3, 2, 4]：逆序发生在3, 2之间，区间内最小值是2，最大值是3。从左找第一个大于2的位置是下标1（元素3），从右找第一个小于3的位置是下标2（元素2），长度为2 - 1 + 1 = 2，正确。

再看一个更微妙的反例[2, 3, 3, 2, 4]：若直接取"第一个降序点"会得到3（下标 1）附近，但实际需要排序的区间是[3, 3, 2]，因为2必须插入到两个3之前，左边界应还原到下标1（第一个大于区间最小值2的元素）。这正是"还原边界"步骤存在的意义。

源码实现逐段精讲

完整代码

核心实现位于 leetcode/0581.Shortest-Unsorted-Continuous-Subarray/581. Shortest Unsorted Continuous Subarray.go，与 README 中的代码一致：

package leetcode import "math" func findUnsortedSubarray(nums []int) int { n, left, right, minR, maxL, isSort := len(nums), -1, -1, math.MaxInt32, math.MinInt32, false // left for i := 1; i < n; i++ { if nums[i] < nums[i-1] { isSort = true } if isSort { minR = min(minR, nums[i]) } } isSort = false // right for i := n - 2; i >= 0; i-- { if nums[i] > nums[i+1] { isSort = true } if isSort { maxL = max(maxL, nums[i]) } } // minR for i := 0; i < n; i++ { if nums[i] > minR { left = i break } } // maxL for i := n - 1; i >= 0; i-- { if nums[i] < maxL { right = i break } } if left == -1 || right == -1 { return 0 } return right - left + 1 } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b }

阶段一：从左向右求区间内最小值minR

for i := 1; i < n; i++ { if nums[i] < nums[i-1] { isSort = true } if isSort { minR = min(minR, nums[i]) } }

• isSort作为"是否已经进入乱序区"的开关：一旦出现nums[i] < nums[i-1]（下降沿），之后的所有元素都属于需要纳入考虑的乱序范围；
• minR初始化为math.MaxInt32，从下降沿之后持续取min，最终得到逆序区间内（及之后）的最小值。

阶段二：从右向左求区间内最大值maxL

isSort = false for i := n - 2; i >= 0; i-- { if nums[i] > nums[i+1] { isSort = true } if isSort { maxL = max(maxL, nums[i]) } }

• 方向相反、判定条件对称：一旦出现nums[i] > nums[i+1]（从左看是下降沿），从该位置向左的所有元素纳入范围；
• maxL初始化为math.MinInt32，不断取max，得到逆序区间内（及左侧）的最大值。

阶段三：还原左边界

for i := 0; i < n; i++ { if nums[i] > minR { left = i break } }

从左到右找到第一个大于minR的元素下标。它之前的所有元素都不大于minR，与minR组合依然有序，因此这个位置才是逆序区间的起点。

阶段四：还原右边界

for i := n - 1; i >= 0; i-- { if nums[i] < maxL { right = i break } }

从右到左找到第一个小于maxL的元素下标。它之后的所有元素都不小于maxL，与maxL组合依然有序，因此这是逆序区间的终点。

结果输出与边界处理

if left == -1 || right == -1 { return 0 } return right - left + 1

• 若数组已整体有序，两个"还原"循环都不会触发（minR仍为MaxInt32、maxL仍为MinInt32，或没有元素满足大小关系），left、right保持-1，直接返回0；
• 否则返回闭区间[left, right]的长度right - left + 1。

复杂度分析

• 时间复杂度：O(n)：四趟线性扫描（两次统计 + 两次还原边界），每趟最多遍历整个数组，总代价为 O(n)；
• 空间复杂度：O(1)：只使用了left、right、minR、maxL、isSort等常数个变量，未申请任何与 n 相关的辅助空间。

注意 README 约束中nums[i]的取值范围为[-10^5, 10^5]，因此用math.MaxInt32/math.MinInt32作为"未进入乱序区"的哨兵值是安全且不会溢出的。

测试用例与运行验证

仓库中的单元测试

测试文件 leetcode/0581.Shortest-Unsorted-Continuous-Subarray/581. Shortest Unsorted Continuous Subarray_test.go 采用仓库统一的表格驱动风格：先用para581/ans581结构体封装输入与期望输出，再在Test_Problem581中逐条断言。

qs := []question581{ { para581{[]int{2, 6, 4, 8, 10, 9, 15}}, ans581{5}, }, { para581{[]int{1, 2, 3, 4}}, ans581{0}, }, { para581{[]int{1}}, ans581{0}, }, }

三个用例分别覆盖三类典型场景：

测试运行时会打印输入与输出对照（fmt.Printf），便于人工核对：

【input】:[2 6 4 8 10 9 15] 【output】:5 【input】:[1 2 3 4] 【output】:0 【input】:[1] 【output】:0

如何运行测试

在仓库根目录执行单测，验证本题实现：

go test -v ./leetcode/0581.Shortest-Unsorted-Continuous-Subarray/ -run Test_Problem581

若希望跑完整仓库测试并生成覆盖率文件，可参考仓库根目录 gotest.sh 中的写法（Go 1.10+ 支持一次对多个包产出合法 profile）：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

举一反三：边界条件的进一步思考

1. 首尾已有序但中间乱序：例如[1, 5, 3, 4, 9]，逆序区间是[5,3,4]。阶段一从5>1处的下降沿开始记录，minR = 3；阶段二从4<9向左，maxL = 5。还原时从左找第一个大于3的位置是下标1，从右找第一个小于5的位置是下标3，长度3，正确。
2. 重复元素：例如[2, 2, 2, 1]，minR = 1，左边界还原为下标0（第一个大于1的元素），右边界还原为下标3（最后一个小于2的元素……实际为1），长度4，即整个数组都需要排序，符合直觉。
3. 为什么不能只用"相邻逆序对"判断：因为某个"小元素"可能需要跨越多个已有序元素向左移动，例如[3, 4, 2]中2要移动到最前面，相邻逆序只出现在4 > 2一处，但实际排序区间覆盖整个数组。这正是"用区间内最值还原边界"替代"局部逆序点"的根本原因。

小结

本题的解法脉络可以浓缩为一条主线：乱序区间的"影响力"由区间内的最小值和最大值决定——最小值决定它能向左影响到哪里，最大值决定它能向右影响到哪里。基于此，LeetCode-Go 仓库中的实现用四趟线性扫描（统计minR/maxL→ 还原left/right）完成了 O(n) 时间、O(1) 空间的求解，并通过表格驱动单测验证了题目给出的全部示例。无论是应对面试中的边界追问，还是为类似"找最短需排序区间"类问题积累模板，这套思路都值得熟练掌握。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go