最短无序连续子数组

问题拆解

要找出最短的连续子数组，只要把它排好序，整个数组就有序，返回它的长度。

一个很自然的做法：把数组复制一份排序，再从两端向中间比对，第一处和最后一处与原数组不同的位置就框定了无序段。它正确、好写，但排序带来 O(n log n) 的时间。进阶希望做到 O(n)，就得想清楚：到底是什么让一个元素“必须被重排”。

如果某个元素比它左边出现过的最大值还小，它就站错了位置，无序段的右边界至少要到它这里；对称地，比右边最小值还大的元素，界定了左边界。

排序后比对（作为对照）

def findUnsortedSubarray(nums):
    sorted_nums = sorted(nums)
    left, right = 0, len(nums) - 1
    while left <= right and nums[left] == sorted_nums[left]:
        left += 1
    while right >= left and nums[right] == sorted_nums[right]:
        right -= 1
    return right - left + 1

这版本把“哪里开始乱、哪里结束”交给排序去回答，思路清楚，适合先建立直觉。瓶颈只在排序的 O(n log n)。

两趟扫描定位边界

从左往右维护“到目前为止的最大值” max_seen：一旦当前元素比它小，说明这个元素被更大的数越过了，把右边界 right 更新到这里。从右往左维护“到目前为止的最小值” min_seen：当前元素比它大，就把左边界 left 更新到这里。

def findUnsortedSubarray(nums):
    n = len(nums)
    right = -1
    max_seen = nums[0]
    for i in range(n):
        if nums[i] < max_seen:
            right = i
        else:
            max_seen = nums[i]

    left = n
    min_seen = nums[-1]
    for i in range(n - 1, -1, -1):
        if nums[i] > min_seen:
            left = i
        else:
            min_seen = nums[i]

    return right - left + 1 if right != -1 else 0

两遍扫描各自找到最靠右的“偏小元素”和最靠左的“偏大元素”，它们之间就是必须重排的区间。以 [2,6,4,8,10,9,15] 为例：从左看 4、9 依次小于此前的最大值，右边界停在下标 5；从右看 10、6 依次大于其右侧最小值，左边界停在下标 1，区间长度 5 - 1 + 1 = 5。若数组本就有序，第一趟不会更新 right，它保持初始的 -1，直接返回 0。

复杂度

指标	复杂度	原因
时间	O(n)	左右各扫一遍
空间	O(1)	只维护边界与极值

可以迁移的模式

• 需要判断“哪些元素破坏了单调性”；
• 一个方向的信息不够，就正反两趟分别维护历史极值；
• 用越界元素反推区间边界，避免真的去排序。

“最多交换一段使数组有序”“判断能否通过一次翻转变有序”都能借这种双向扫描的视角来想。