LeetCode 面试题 16.16. 部分排序

2022-07-25 HGNULB 约 8 分钟

文章信息 8 个分类 6 个标签

分类

LeetCode CodeTop 中等未解决 2-5 字节跳动快手程序员面试金典（第 6 版）

题目描述

✅ 面试题 16.16. 部分排序

题意分析

给一个整数数组，找出一对下标 [m, n]，只要把这段区间内部升序排好，整个数组就变成非降序的，并且要求这段区间尽可能短；数组本来就有序时返回 [-1, -1]。

第一个信号是不需要真的排序。返回值只有两个下标，排序结果本身没人要，所以任何「先排一份再对比」的做法都在做多余的工作。

第二个信号藏在「最短」两个字里。最短意味着边界是充要的：区间里的每个元素都必须动，区间外的每个元素都必须不动。于是问题从「怎么排」变成了一个纯粹的判定问题——某个位置在最终有序数组里是否还待在原地。

顺着这个判定往下想，位置 i 能原地不动的充要条件是：它左边的所有元素都不比它大，且右边的所有元素都不比它小。这两个条件天然对应两个方向的扫描，也就把一个二维的比较压成了两次一维遍历。

边界：空数组直接返回 [-1, -1]；元素全部相同属于有序，也返回 [-1, -1]；完全逆序时答案是整个数组 [0, n-1]；只有两个元素时两次扫描各只跑一轮。

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

核心思路

最直白的做法是复制一份排好序，再从两头找第一个与原数组不同的位置。它是对的，但要花 $O(n \log n)$ 时间和 $O(n)$ 额外空间，而且做了远超需要的事——我们只想知道「哪些位置和排序后不一致」，并不想知道排序后长什么样。

瓶颈在于把「是否需要移动」这个局部判定，交给了排序这个全局操作。回到上面那条充要条件，它其实可以只用前缀最大值和后缀最小值表达：

若 array[i] < max(array[0..i-1])，说明 i 左边存在比它大的元素，i 必须被排进区间；从左往右扫，最后一次满足这个条件的下标就是右边界 right——它右边再没有任何位置违反非降序，所以区间不必再往右延伸。

对称地，若 array[i] > min(array[i+1..n-1])，说明 i 右边存在比它小的元素，i 也必须被排进区间；从右往左扫，最后一次满足条件的下标就是左边界 left。

循环不变量是：正向扫描到 i 时，maxVal 恒等于 array[0..i-1] 的最大值。代码里在 array[i] < maxVal 的分支中没有更新 maxVal，看似漏了一步，其实正因为此时 array[i] < maxVal，更新与否 maxVal 都不会变，两种写法完全等价。反向扫描的 minVal 同理。

最后需要确认这个区间既充分又最短。区间外的位置按定义左侧全不比它大、右侧全不比它小，排序后必然停在原地，所以不需要包含它们，这保证了最短；而区间内的元素排序后一定还落在区间内（区间外的元素相对位置不变，且已经形成了包夹），所以只排这一段就够了，这保证了充分。

解题步骤

空数组直接返回 [-1, -1]：后面两次扫描都要先取 array[0] 和 array[n-1] 作初值，不挡一下会直接越界。

left 与 right 都初始化为 -1：这个初值同时承担了「答案」的角色。数组本来有序时两次扫描一次都不会赋值，返回的正好是题目要求的 [-1, -1]，不需要额外判断有序性。

正向扫描定右边界：maxVal 取 array[0]，i 从 1 开始；array[i] < maxVal 时把 right 更新成 i（注意是覆盖式赋值，不是 break，因为要的是最后一次），否则把 maxVal 抬到 array[i]。

比较必须用严格小于：相等不破坏非降序，array[i] == maxVal 的位置是可以原地不动的，用 <= 会把它错误地圈进区间，违反「最短」。

反向扫描定左边界：minVal 取 array[n-1]，i 从 n-2 递减；array[i] > minVal 时更新 left，否则下调 minVal。这一趟必须重新初始化 minVal，它和正向那趟没有任何共享状态。

返回 [left, right]：左边界来自反向扫描、右边界来自正向扫描，两者不能互换。

以 [2, 6, 4, 8, 10, 9, 15] 走一遍（正确答案是 [1, 5]）。

正向扫描，maxVal 初值 2、right 初值 -1：

i = 1，6 ≥ 2 → 不越界，maxVal = 6

i = 2，4 < 6 → 4 的左边有更大的 6，必须移动，right = 2；maxVal 保持 6

i = 3，8 ≥ 6 → maxVal = 8

i = 4，10 ≥ 8 → maxVal = 10

i = 5，9 < 10 → right = 5（覆盖掉之前的 2）

i = 6，15 ≥ 10 → maxVal = 15，扫描结束，right = 5

反向扫描，minVal 初值 15、left 初值 -1：

i = 5，9 > 15 不成立 → minVal = 9

i = 4，10 > 9 → 10 的右边有更小的 9，必须移动，left = 4

i = 3，8 > 9 不成立 → minVal = 8

i = 2，4 > 8 不成立 → minVal = 4

i = 1，6 > 4 → left = 1（覆盖掉之前的 4）

i = 0，2 > 4 不成立 → minVal = 2，扫描结束，left = 1

返回 [1, 5]，把 [6, 4, 8, 10, 9] 排好后数组变成 [2, 4, 6, 8, 9, 10, 15]，确实有序。再看有序输入 [1, 2, 3]：正向每一步都满足 array[i] ≥ maxVal，反向每一步都不满足 array[i] > minVal，两个边界一次都没被赋值，返回 [-1, -1]。

代码实现

class Solution {
    // 从左到右维护已扫描最大值，若当前值小于这个最大值，说明它必须被纳入待排序区间，右边界更新到当前位置。
    public int[] subSort(int[] array) {
        int n = array.length;
        if (n == 0) {
            return new int[]{-1, -1};
        }

        int left = -1;
        int right = -1;

        int maxVal = array[0];
        for (int i = 1; i < n; i++) {
            if (array[i] < maxVal) {
                right = i;
            } else {
                maxVal = array[i];
            }
        }

        int minVal = array[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            if (array[i] > minVal) {
                left = i;
            } else {
                minVal = array[i];
            }
        }

        return new int[]{left, right};
    }
}

func subSort(array []int) []int {
    // 从左到右维护已扫描最大值，若当前值小于这个最大值，说明它必须被纳入待排序区间，右边界更新到当前位置。
    if len(array) == 0 {
        return []int{-1, -1}
    }

    left, right := -1, -1

    maxVal := array[0]
    for i := 1; i < len(array); i++ {
        if array[i] < maxVal {
            right = i
        } else {
            maxVal = array[i]
        }
    }

    minVal := array[len(array)-1]
    for i := len(array) - 2; i >= 0; i-- {
        if array[i] > minVal {
            left = i
        } else {
            minVal = array[i]
        }
    }

    return []int{left, right}
}

复杂度分析

时间复杂度：$O(n)$，两趟独立的线性扫描，每趟每个元素只做一次比较和至多一次赋值，没有嵌套循环。

空间复杂度：$O(1)$，只用了 left、right、maxVal、minVal 四个标量，没有复制数组，这正是它相对「排序后对比」写法的核心优势。

关键点总结

「最短区间」类问题的通用切入点是把它翻译成逐位置的判定：这个位置在最终答案里动不动？一旦翻译成功，往往就能用前缀 / 后缀的极值一次扫描解决。

两个边界由两个方向分别负责，右边界来自正向扫描、左边界来自反向扫描。面试时把这句话先说出来，能立刻证明你没把方向搞混——这是现场最容易口误的地方。

判定用严格不等号，相等不算逆序。区间的「最短」性完全靠这一点保证。

-1 初值让「数组已经有序」自然落进主逻辑，不需要先跑一趟有序性检查；能不特判就不特判是好实现的标志。

面试官很可能追问「为什么这个区间是最短的」，标准答法是分两半论证：区间外的元素排序后不动（所以不必更长），区间内的元素排序后仍落在区间内（所以已经够长）。

易错点总结

正向判定写成 array[i] <= maxVal：输入 [1, 2, 2, 3] 本来有序，却会在 i = 2 处记下 right = 2，返回一个不合法的区间。

反向判定写成 array[i] >= minVal：同一个 [1, 2, 2, 3] 会得到 left = 1，同样把有序数组判成需要排序。

minVal 初始化成 array[0] 或与正向共用 maxVal：输入 [2, 1] 时反向那趟的初值就是错的，left 保持 -1，返回 [-1, 1]——只有一个边界的区间毫无意义。

maxVal 初始化成 0：输入 [-3, -2, -1] 已经有序，但每个元素都小于 0，会一路把 right 推到 2，返回 [-1, 2]。

只比较相邻元素（array[i] < array[i-1] 才更新 right）：输入 [1, 5, 2, 3, 4] 只有 i = 2 处相邻下降，得到 right = 2，而正确右边界是 4——5 要一直挪到末尾去。前缀最大值和相邻比较不是一回事。

命中条件后 break：输入 [2, 6, 4, 8, 10, 9, 15] 正向第一次命中就停，right = 2 而不是 5，区间被截短。要的是最后一次命中，所以必须扫完。

左右边界赋反（把正向结果当 left）：同样的输入会返回 [5, 1]，区间左大于右，直接是空区间。

只扫一趟就返回：输入 [2, 1] 只做正向扫描得 right = 1，left 仍是 -1，返回 [-1, 1]。两个方向缺一不可。

空数组不挡：输入 [] 时 array[0] 直接抛越界异常。

偷懒排序后逐位比较：结果虽然对，但 $n$ 到 $10^6$ 时比两趟扫描慢一个数量级，还多占 $O(n)$ 空间，面试官必然追问能不能做到线性。

相似题目

题目	难度	考察点
581. 最短无序连续子数组	中等	与本题解法逐行相同，只是返回区间长度而非下标，有序时返回 0
238. 除了自身以外数组的乘积	中等	同为前后缀信息两趟扫描，把「取最值」换成「累乘」并要求 $O(1)$ 额外空间
42. 接雨水	困难	每个位置都要用到前缀最大与后缀最大的具体数值，本题只需要它们参与一次比较
121. 买卖股票的最佳时机	简单	只维护前缀最小值的单侧简化版，一趟扫描即可，无需反向补一趟
739. 每日温度	中等	同样问「右侧更大的元素」，但要逐位置给出答案，只能用单调栈而非全局极值
152. 乘积最大子数组	中等	也是扫描中维护极值，但必须同时维护最大与最小以应对负号翻转