LeetCode 面试题 16.16. 部分排序

约 5 分钟
文章信息 8 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 程序员面试金典（第 6 版） 字节 快手
标签
数组 排序 双指针 栈 贪心 单调栈

题目描述

✅ 面试题 16.16. 部分排序

image-20260928231110786

题意分析

找到数组中最短的连续区间 [left, right]，只把这个区间内部排序，整个数组就能成为非递减序列，返回左右下标。区间外的元素保持原位置，不需要实际执行排序。

相等值不破坏有序性。数组已经有序时返回 [-1, -1]，空数组也无需排序。目标区间里并不是每个元素都必须移动，而是这个连续范围必须覆盖所有造成整体无序的位置。

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

核心思路

[!blue]

如果存在 i < j 但 array[i] > array[j]，这两个位置形成逆序。任何能够修复数组的排序区间，都必须同时包含这对位置：若有一端留在区间外，区间内再怎么重排，也无法让这个较大的值和较小的值跨过彼此，逆序仍会存在。

从左到右维护已经扫描部分的最大值 maxVal。当前位置小于它，说明左边至少有一个更大的值，当前位置是逆序对的右端，待排序区间必须延伸到这里。持续更新 right，最后得到所有必要右端中最靠右的一个；当前位置不小于最大值时，再更新前缀最大值。

从右到左对称处理，维护后缀最小值 minVal。当前位置大于它，说明右边存在更小值，当前位置是必要的左端，更新 left。扫描方向向左，最终保留的就是所有必要左端中最靠左的一个。

这两个边界为什么也足够？它们包含了所有逆序对的两端，因而区间外不存在尚未包含的内部逆序或跨边界逆序。左侧保留部分的值不大于区间内任何值，右侧保留部分的值不小于区间内任何值；把区间内部排好后，三部分便能顺序连接成完整有序数组。

所有可行区间都必须覆盖这两个最外侧的必要端点，而它们之间的区间本身又可行，因此它就是最短区间。若一次逆序都没有发现，左右边界保留 -1，表示无需排序。

解题步骤

  1. 空数组直接返回 [-1, -1]；否则将左右答案边界初始化为 -1。
  2. 从首元素初始化前缀最大值，向右扫描。当前值小于前缀最大值时更新 right，否则更新最大值。
  3. 从末元素初始化后缀最小值，向左扫描。当前值大于后缀最小值时更新 left，否则更新最小值。
  4. 返回 [left, right]，原数组不作修改。

代码实现

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)$，只保存两个极值、两个边界和固定长度的返回数组，不复制或排序输入。

关键点总结

[!green]

  • 前缀最大值发现逆序的必要右端，后缀最小值发现必要左端。
  • 包含所有逆序端点是必要条件，也是排序该区间即可修复全局的充分条件。
  • 使用严格大小比较，重复且相等的值本身不要求扩展区间。

易错点总结

[!yellow]

  • 只比较相邻元素，会遗漏距离较远的逆序对，截短真正需要一起排序的区间。
  • 第一次发现逆序就停止，会漏掉更外侧的必要端点，应完成两个方向的扫描。
  • 用零初始化极值，会在全负数或全正数等情况下混入数组外的错误比较基准，应从实际元素初始化。
  • 用小于等于或大于等于判逆序，会把相等元素也当成无序，破坏最短性。
  • 在空数组上读取首尾元素会越界，必须先处理空输入。

相似题目

题目 难度 关联与区别
581. 最短无序连续子数组 中等 边界判定相同，原题只返回区间长度，本题返回左右下标并用[-1,-1]表示已有序。
915. 分割数组 中等 同样利用前缀最大值与后缀最小值判断跨边界无序，本题要定位必须一起排序的最短区域。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/68408313
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！