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

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

题目描述

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

题意分析

给定一个整数数组 nums，要找出一个最短的连续子数组，使得只把这一段就地升序排好，整个数组就变成升序；返回这段子数组的长度，若数组本身已经有序则返回 0。

「最短」意味着答案是一个区间 [left, right]，必须同时把左右两个端点都钉死才能算出长度。只找到某一侧的越界位置是不够的 —— 破坏顺序的元素可能一部分偏左、一部分偏右，区间要同时向两边张开。

约束信号是题目所说的「升序」允许相等，也就是非递减，所以相邻的重复元素并不破坏顺序，所有判据都得用严格不等号。

边界包括：数组本身已经有序；数组长度为 1；全部元素相同；待排序区间紧贴数组开头或结尾；数组里有大量重复值。

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

核心思路

排序副本后找首尾差异可以解题，但需要 $O(n \log n)$ 时间和 $O(n)$ 空间。其实无需知道排序后的每个值，只需判断哪些位置必然要移动。

  • 从左向右维护前缀最大值 maxSeen。若 nums[i] < maxSeen，说明左侧有更大的数必须越过 i，于是 i 必在待排序区间内，用它更新右边界 right。
  • 从右向左维护后缀最小值 minSeen。若 nums[i] > minSeen，说明右侧有更小的数必须越过 i，于是用它更新左边界 left。

扫描不变量分别是：right 始终是已发现的最右违规位置，left 始终是已发现的最左违规位置。两端之外没有跨越它们的逆序关系，因此只排序 [left, right] 就能使全数组有序；两端本身又都被证明必须移动，所以该区间最短。

解题步骤

  1. 初始化 right = -1，从左向右扫描；遇到 nums[i] < maxSeen 就更新 right，否则更新前缀最大值。
  2. 初始化 left = n，从右向左扫描；遇到 nums[i] > minSeen 就更新 left，否则更新后缀最小值。
  3. right == -1 表示从未发现违规位置，数组已有序，返回 0；否则返回闭区间长度 right - left + 1。

例如 [2,6,4,8,10,9,15]：正向扫描得到 right = 5，反向扫描得到 left = 1，答案为 5。注意判据使用严格不等号，重复值不破坏非递减顺序。

代码实现

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)$，只使用常数个变量。

关键点总结

  • 右边界看前缀最大值，左边界看后缀最小值，两次扫描缺一不可。
  • 相等不算逆序，判断必须是 < 和 >。
  • 用 right = -1 同时表达空区间和数组已有序，无需额外检查。
  • 面试时可先说排序基线，再推导到线性扫描；单调栈也能做，但会多用 $O(n)$ 空间。

易错点总结

  • 只比较相邻元素会漏掉远距离逆序，如 [1,3,2,2,2] 的答案是 4，不是 2。
  • 用 <=、>= 会把重复值误判为无序；[1,2,2,3] 应返回 0。
  • 极值初值不能写成 0，否则全负数组会误判。
  • 返回的是闭区间长度，必须加 1。

相似题目

题目 难度 考察点
665. 非递减数列 中等 至多一次修改能否有序
1574. 删除最短的子数组使剩余数组有序 中等 删除最短子段后拼接有序
面试题 16.16. 部分排序 中等 同题改为返回左右下标