最短无序连续子数组 图解题解

这道题真正在问什么

给一个整数数组，找出最短的一段连续子数组，使得只把这一段升序排序后，整个数组就有序，返回这段的长度；数组本来就有序时返回 0。注意求的是长度不是内容，而且这段必须连续——问题实质是定位两个边界：最左边那个必须动的位置，和最右边那个必须动的位置，答案就是两者的距离加一。

排序后逐位比对为什么不是最优解

最直观的做法：把数组复制一份排好序，和原数组逐位比对，左起第一个不同的位置是左边界、右起第一个不同的位置是右边界。这个思路完全正确，但排序花掉 O(n log n) 时间、副本花掉 O(n) 空间，都是浪费——我们并不需要知道排好后每个位置具体是什么数，只需要判断「哪些位置不在它该在的地方」，而这个判断有更便宜的办法。

什么样的位置一定要被重排

换个角度看「有序」的定义：数组升序，等价于每个数都不小于它左边的所有数。所以从左往右扫，维护一个「到目前为止的最大值 maxv」，一旦当前数比 maxv 还小，说明左边有更大的数压着它，这个位置必须被卷进重排区间。所有这样的位置里最靠右的那个，就是右边界 right——right 右边的数全都不小于左侧最大值，本来就各就各位。

左边界完全对称：升序也等价于每个数都不大于它右边的所有数。从右往左扫，维护「此后最小值 minv」，凡是比 minv 还大的位置都必须动，其中最靠左的那个就是左边界 left。

为什么必须分两遍、方向相反地扫

右边界依赖「从左到右一路累积的最大值」，左边界依赖「从右到左一路累积的最小值」——两个量的累积方向相反，一趟单向扫描只攒得出其中一个，所以必须各扫一遍。两遍都是不嵌套的纯线性扫描，总时间仍是 O(n)，并没有因为多扫一遍而升级复杂度。

复杂度与最容易翻车的边界

时间 O(n)：两趟线性扫描各走一遍数组。空间 O(1)：只用 maxv、minv、left、right 四个变量，不开副本。最容易翻车的边界是数组本来就有序：这时第一遍扫描里永远不会出现「当前数小于 maxv」，right 保持初值 -1，必须直接返回 0，忘了这个判断就会拿未更新的边界算出荒谬的长度。另外相等元素不算乱：判断用的是严格小于和严格大于，像 [1,2,2,3] 这种带重复值的有序数组会正确地返回 0。

Python

def findUnsortedSubarray(nums):
    n = len(nums)
    maxv, right = float("-inf"), -1
    for i in range(n):              # 从左扫找右边界
        if nums[i] < maxv: right = i   # 比前面最大值还小=乱
        else: maxv = nums[i]
    minv, left = float("inf"), n
    for i in range(n - 1, -1, -1): # 从右扫找左边界
        if nums[i] > minv: left = i    # 比后面最小值还大=乱
        else: minv = nums[i]
    return 0 if right == -1 else right - left + 1

C++

int findUnsortedSubarray(vector<int>& nums){
    int n = nums.size();
    int maxv = INT_MIN, right = -1;
    for(int i = 0; i < n; i++){         // 从左扫找右边界
        if(nums[i] < maxv) right = i;    // 比前面最大值还小=乱
        else maxv = nums[i];
    }
    int minv = INT_MAX, left = n;
    for(int i = n - 1; i >= 0; i--){    // 从右扫找左边界
        if(nums[i] > minv) left = i;     // 比后面最小值还大=乱
        else minv = nums[i];
    }
    return right == -1 ? 0 : right - left + 1;
}

Java

public int findUnsortedSubarray(int[] nums) {
    int n = nums.length;
    int maxv = Integer.MIN_VALUE, right = -1;
    for (int i = 0; i < n; i++) {        // 从左扫找右边界
        if (nums[i] < maxv) right = i;    // 比前面最大值还小=乱
        else maxv = nums[i];
    }
    int minv = Integer.MAX_VALUE, left = n;
    for (int i = n - 1; i >= 0; i--) {   // 从右扫找左边界
        if (nums[i] > minv) left = i;     // 比后面最小值还大=乱
        else minv = nums[i];
    }
    return right == -1 ? 0 : right - left + 1;