LeetCode 581. 最短无序连续子数组

约 5 分钟
文章信息 12 个分类 6 个标签
分类
LeetCode CodeTop 中等 已解决 10-20 腾讯 字节 阿里 小米 快手 滴滴 旷视
标签
数组 排序 双指针 栈 贪心 单调栈

题目描述

✅ 581. 最短无序连续子数组

image-20260928221054526

image-20260928221054527

题意分析

选择一个尽量短的连续区间，只将这段元素按非递减顺序排序，就能使整个数组非递减，返回该区间的长度。区间外的元素不移动；数组原本有序时返回零。

非递减允许相邻元素相等。无序影响不只发生在相邻位置，一个偏大的值可能需要跨过多个元素才能归位，所以需要找到全部逆序关系必须覆盖的最左、最右位置。

解法：双向扫描确定左右边界

核心思路

[!blue]

若存在 i < j 且 nums[i] > nums[j]，就有一对逆序。要通过排序一段连续区间消除它，这两个位置都必须被包含：若将右端位置留在区间外，左边那个更大的元素仍留在它前面的某处；将左端位置留在区间外时也同理。

从左到右扫描，用 maxSeen 保存此前元素的最大值。若 nums[i] < maxSeen，当前位置就是某对逆序的右端，待排序区间必须延伸到这里，因此更新 right = i。持续覆盖后，right 是所有逆序右端中最靠右的位置。

从右到左同理，用 minSeen 保存后面元素的最小值。若 nums[i] > minSeen，当前位置是逆序左端，就更新 left = i，最终得到最靠左的必要位置。相等不构成逆序，不能使用非严格比较。

得到的 [left, right] 不仅必要，也足够：任何逆序的两端都在这个区间内，区间外本身有序，也不存在跨过左右边界的逆序。将内部排序后，内部逆序消失，区间内外的数值集合不变，因此边界也仍满足顺序，整个数组就有序了。

所有可行区间都必须覆盖这两个极端位置，而排序它们之间的区间已经足够，所以长度最短。用 right = -1 表示尚未发现逆序；若扫描后仍为这个值，直接返回零，否则返回 right - left + 1。

解题步骤

  1. 初始化 right = -1、maxSeen 为整数最小值，从左到右扫描；当前值更小时更新右边界，否则更新前缀最大值。
  2. 初始化 left = n、minSeen 为整数最大值，从右到左扫描；当前值更大时更新左边界，否则更新后缀最小值。
  3. 若 right == -1，说明数组已经非递减，返回零。
  4. 否则返回闭区间长度 right - left + 1，无需实际排序或修改数组。

代码实现

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int 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 = n;
        int minSeen = Integer.MAX_VALUE;

        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] > minSeen) {
                // 当前位置大于后缀最小值，待排序区间必须覆盖这个逆序端点。
                left = i;
            } else {
                minSeen = nums[i];
            }
        }

        if (right == -1) {
            return 0;
        }

        return right - left + 1;
    }
}

func findUnsortedSubarray(nums []int) int {
    n := len(nums)
    minInt := -int(^uint(0)>>1) - 1
    maxInt := int(^uint(0) >> 1)

    right := -1
    maxSeen := minInt
    for i := 0; i < n; i++ {
        if nums[i] < maxSeen {
            // 当前值小于左侧最大值，说明它必须进入待排序区间。
            right = i
        } else {
            maxSeen = nums[i]
        }
    }

    left := n
    minSeen := maxInt
    for i := n - 1; i >= 0; i-- {
        if nums[i] > minSeen {
            // 当前位置大于后缀最小值，待排序区间必须覆盖这个逆序端点。
            left = i
        } else {
            minSeen = nums[i]
        }
    }

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

复杂度分析

  • 时间复杂度：$O(n)$，两次线性扫描。
  • 空间复杂度：$O(1)$，只使用常数个变量。

关键点总结

[!green]

  • 右边界看前缀最大值，左边界看后缀最小值，两次扫描缺一不可。
  • 相等不算逆序，判断必须是 < 和 >。
  • 用 right = -1 同时表达空区间和数组已有序，无需额外检查。

易错点总结

[!yellow]

  • 只检查相邻逆序会忽略较大值与远处较小值的关系，边界可能收得过窄。
  • 使用 <= 或 >= 会把允许存在的重复值误判为无序，应采用严格比较。
  • 前缀最大值和后缀最小值不能都从零开始，否则负数或正数输入可能产生虚假的逆序。
  • 已有序时要先返回零，不能用未初始化成有效区间的左右边界计算长度。
  • 返回的是闭区间包含的元素数，因此两端下标相减后还要加一。

相似题目

题目 难度 关联与区别
915. 分割数组 中等 同样利用左侧最大值与右侧最小值判定是否有跨边界逆序，本题要同时确定最短待排序区间的两端。
769. 最多能完成排序的块 中等 同样分析哪些区间能独立排序，本题只允许排序一个连续段，原题尽可能划分多个块。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/55935806
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！