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 中给出了如下示例示例 1Input: 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.示例 2Input: nums [1,2,3,4] Output: 0示例 3Input: 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[i1]之类的相邻关系排序这段区间后它内部的最小值会被放到区间最左端最大值会被放到区间最右端因此最短逆序区间的左边界取决于第一个被区间内最小值影响到的位置右边界取决于最后一个被区间内最大值影响到的位置。四步扫描策略README 思路的完整展开README 中给出了一个清晰的 O(n) 思路可以拆解为四个阶段从左向右扫描确定逆序区间内的最小元素min找到第一个降序点nums[i] nums[i-1]之后持续记录后续元素中的最小值记为minR。从右向左扫描确定逆序区间内的最大元素max找到第一个右侧降序点nums[i] nums[i1]之后持续记录左侧元素中的最大值记为maxL。还原左边界从左往右找到第一个大于minR的元素位置这才是逆序区间的真正左边界。还原右边界从右往左找到第一个小于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[i1] { 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 }阶段一从左向右求区间内最小值minRfor 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最终得到逆序区间内及之后的最小值。阶段二从右向左求区间内最大值maxLisSort false for i : n - 2; i 0; i-- { if nums[i] nums[i1] { isSort true } if isSort { maxL max(maxL, nums[i]) } }方向相反、判定条件对称一旦出现nums[i] nums[i1]从左看是下降沿从该位置向左的所有元素纳入范围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}, }, }三个用例分别覆盖三类典型场景输入期望输出场景说明[2,6,4,8,10,9,15]5中间乱序需要排序[6,4,8,10,9][1,2,3,4]0整体已升序[1]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 支持一次对多个包产出合法 profilego test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...举一反三边界条件的进一步思考首尾已有序但中间乱序例如[1, 5, 3, 4, 9]逆序区间是[5,3,4]。阶段一从51处的下降沿开始记录minR 3阶段二从49向左maxL 5。还原时从左找第一个大于3的位置是下标1从右找第一个小于5的位置是下标3长度3正确。重复元素例如[2, 2, 2, 1]minR 1左边界还原为下标0第一个大于1的元素右边界还原为下标3最后一个小于2的元素……实际为1长度4即整个数组都需要排序符合直觉。为什么不能只用相邻逆序对判断因为某个小元素可能需要跨越多个已有序元素向左移动例如[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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
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 中给出了如下示例示例 1Input: 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.示例 2Input: nums [1,2,3,4] Output: 0示例 3Input: 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[i1]之类的相邻关系排序这段区间后它内部的最小值会被放到区间最左端最大值会被放到区间最右端因此最短逆序区间的左边界取决于第一个被区间内最小值影响到的位置右边界取决于最后一个被区间内最大值影响到的位置。四步扫描策略README 思路的完整展开README 中给出了一个清晰的 O(n) 思路可以拆解为四个阶段从左向右扫描确定逆序区间内的最小元素min找到第一个降序点nums[i] nums[i-1]之后持续记录后续元素中的最小值记为minR。从右向左扫描确定逆序区间内的最大元素max找到第一个右侧降序点nums[i] nums[i1]之后持续记录左侧元素中的最大值记为maxL。还原左边界从左往右找到第一个大于minR的元素位置这才是逆序区间的真正左边界。还原右边界从右往左找到第一个小于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[i1] { 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 }阶段一从左向右求区间内最小值minRfor 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最终得到逆序区间内及之后的最小值。阶段二从右向左求区间内最大值maxLisSort false for i : n - 2; i 0; i-- { if nums[i] nums[i1] { isSort true } if isSort { maxL max(maxL, nums[i]) } }方向相反、判定条件对称一旦出现nums[i] nums[i1]从左看是下降沿从该位置向左的所有元素纳入范围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}, }, }三个用例分别覆盖三类典型场景输入期望输出场景说明[2,6,4,8,10,9,15]5中间乱序需要排序[6,4,8,10,9][1,2,3,4]0整体已升序[1]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 支持一次对多个包产出合法 profilego test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...举一反三边界条件的进一步思考首尾已有序但中间乱序例如[1, 5, 3, 4, 9]逆序区间是[5,3,4]。阶段一从51处的下降沿开始记录minR 3阶段二从49向左maxL 5。还原时从左找第一个大于3的位置是下标1从右找第一个小于5的位置是下标3长度3正确。重复元素例如[2, 2, 2, 1]minR 1左边界还原为下标0第一个大于1的元素右边界还原为下标3最后一个小于2的元素……实际为1长度4即整个数组都需要排序符合直觉。为什么不能只用相邻逆序对判断因为某个小元素可能需要跨越多个已有序元素向左移动例如[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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
