LeetCode 1574. 删除最短的子数组使剩余数组有序

约 5 分钟
文章信息 7 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 微软
标签
数组 双指针 二分查找 栈 单调栈

题目描述

✅ 1574. 删除最短的子数组使剩余数组有序

image-20260928230607184

image-20260928230607185

题意分析

删除一段连续子数组，可以不删，使剩下的元素按原顺序非递减，求最少删除多少个元素。非递减允许相等，不能把问题改成任意删除若干位置。

删除连续区间以后，剩下的必然是原数组的一个前缀和一个后缀，其中一侧也可以为空。两段各自需要有序，同时还要能在连接处保持非递减。

解法：双指针收缩边界

核心思路

[!blue]

先找最长非递减前缀的末端 left，以及最长非递减后缀的起点 right。任何合法保留前缀都只能在 left 或更早结束，否则会包含前缀之后的降序位置；保留后缀也只能从 right 或更晚开始。因此两侧同时保留时，只需枚举 i <= left、j >= right 的接点。

前缀 0..i 和后缀 j..n-1 内部已经有序，只要 arr[i] <= arr[j]，拼接后也有序。被删除的恰好是两个接点之间的区间，长度为 j-i-1。

固定 i 时，应找最早满足连接条件的 j，因为更靠后的后缀会多删元素。用 i = 0、j = right 开始：若 arr[i] > arr[j]，当前后缀首值太小，必须让 j 右移；若已经能够连接，就更新答案并让 i 右移，尝试保留更长的前缀。

j 不需要退回。随着 i 增加，前缀接点值只会不变或变大，之前因为太小而被跳过的后缀接点仍然不够大。于是每个 i 都能沿同一个右移指针找到最早合法接点，不会漏掉更短删除方案；若 j 已到数组末尾，后续更大的前缀值也不可能再找到接点。

两侧同时保留之外，还要考虑只保留一侧。只留最长有序前缀需删除 n-left-1 个，只留最长有序后缀需删除 right 个，先用二者的较小值初始化答案。若整个数组本来有序，直接返回 0，无需继续寻找删除区间。

解题步骤

  1. 从左向右找到最长非递减前缀末端 left。若已到 n-1，返回 0。
  2. 从右向左找到最长非递减后缀起点 right。
  3. 用 min(n-left-1, right) 初始化答案，覆盖删除末尾或开头的情况。
  4. 令 i = 0、j = right。接点满足 arr[i] <= arr[j] 时，用 j-i-1 更新答案并增加 i；否则增加 j。
  5. 任一指针离开可选范围后结束，返回最小删除长度。

代码实现

class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int left = 0;

        while (left + 1 < n && arr[left] <= arr[left + 1]) {
            left++;
        }

        if (left == n - 1) {
            return 0;
        }

        int right = n - 1;

        while (right > 0 && arr[right - 1] <= arr[right]) {
            right--;
        }

        // 先覆盖只保留有序前缀或只保留有序后缀的方案。
        int res = Math.min(n - left - 1, right);

        int i = 0;
        int j = right;

        while (i <= left && j < n) {
            if (arr[i] <= arr[j]) {
                // 两个保留接点之间才是删除段，不包含接点。
                res = Math.min(res, j - i - 1);
                i++;
            } else {
                // 当前后缀首值太小，只能继续右移寻找可接位置。
                j++;
            }
        }

        return res;
    }
}

func findLengthOfShortestSubarray(arr []int) int {
    n := len(arr)
    left := 0
    for left+1 < n && arr[left] <= arr[left+1] {
        left++
    }
    if left == n-1 {
        return 0
    }

    right := n - 1
    for right > 0 && arr[right-1] <= arr[right] {
        right--
    }

    // 先覆盖只保留有序前缀或只保留有序后缀的方案。
    res := n - left - 1
    if right < res {
        res = right
    }

    i, j := 0, right
    for i <= left && j < n {
        if arr[i] <= arr[j] {
            if j-i-1 < res {
                // 两个保留接点之间才是删除段，不包含接点。
                res = j - i - 1
            }
            i++
        } else {
            // 当前后缀首值太小，只能继续右移寻找可接位置。
            j++
        }
    }

    return res
}

复杂度分析

  • 时间复杂度：$O(n)$。前后缀扫描各为线性，两个接点指针也都只向右移动，不会反复扫描同一范围。
  • 空间复杂度：$O(1)$。只维护前后缀边界、接点和最短长度，不修改原数组。

关键点总结

[!green]

  • 删除一个连续区间，等价于保留一个有序前缀和一个有序后缀。
  • 两段能否连接只需比较接点，内部有序性已经由前后缀边界保证。
  • 固定前缀末端时，最早合法后缀起点删除最少；前缀值不减使这个起点也只会右移。
  • 单侧为空的方案需要单独覆盖，不能只枚举两段都存在的情况。

易错点总结

[!yellow]

  • 使用最长递增子序列，会允许删除不连续的位置，改变题意。
  • 用严格小于判断接点，会拒绝允许的相等值；前后缀扫描也应使用 <=。
  • 删除长度写成 j-i，会把一个保留接点多算进去，正确长度是 j-i-1。
  • 每次同时移动两个接点，可能跳过仍能与同一后缀连接的更长前缀。
  • 忽略只保留前缀或只保留后缀，会漏掉最优删除区间位于数组两端的情况。

相似题目

题目 难度 关联与区别
581. 最短无序连续子数组 中等 原题排序一段，本题删除一段；两题都先定位有序前缀和后缀，但本题还需检查拼接后的边界。
915. 分割数组 中等 原题只找相邻安全分割，本题可删除中间区间后让前后两段有序衔接。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/18356147
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！