LeetCode 1574. 删除最短的子数组使剩余数组有序
目录
题目描述
题意分析
给定整数数组
arr，要求删除恰好一个连续子数组（可以为空），使剩下的元素拼接后是非递减的，问被删子数组的最短长度。「删除的必须是连续的一段」是全题的骨架：设删掉的是 $[l, r]$，那么剩下的就是一个前缀 $[0, l-1]$ 加一个后缀 $[r+1, n-1]$。要让结果非递减，必须同时满足三件事——前缀自身非递减、后缀自身非递减、且前缀的最后一个元素不超过后缀的第一个元素。答案的形态被彻底限定成「保留一个前缀 + 一个后缀」。
注意「非递减」允许相等，所有比较都要用 $\le$ 而不是 $<$，这一点在有重复元素的数组上会直接决定对错。
数据范围 $n \le 10^5$ 说明要 $O(n)$ 或 $O(n \log n)$：枚举 $[l, r]$ 是 $O(n^2)$ 对，即便判定 $O(1)$ 也超时。
边界有三处：数组本身已经非递减时答案为 $0$（删空段）；最坏情况可以删掉 $n - 1$ 个元素只留一个，所以答案上界是 $n-1$，绝不会是 $n$；数组长度为 $1$ 时答案为 $0$。
解法：双指针收缩边界
核心思路
暴力做法是枚举删除区间 $[l, r]$，再检查剩余部分是否有序，$O(n^3)$；用预处理把检查降到 $O(1)$ 也还有 $O(n^2)$ 对区间要枚举。瓶颈在于枚举了大量注定不合法的组合——前缀根本不非递减的 $l$，或后缀根本不非递减的 $r$，怎么配都白搭。
第一个观察把候选范围砍到线性：能保留的前缀必须是原数组「最长非递减前缀」的某个前缀，能保留的后缀必须是「最长非递减后缀」的某个后缀。设最长非递减前缀的末位下标为
left（即arr[0..left]非递减且arr[left] > arr[left+1]），最长非递减后缀的首位下标为right。那么合法方案只有两类：只保留前缀（删掉left+1到 $n-1$，长度 $n - left - 1$）、只保留后缀（删掉 $0$ 到right-1，长度right），或者从两边各取一段拼起来。前两类可以直接算出，重点是第三类。第三类要找的是：在 $i \in [0, left]$、$j \in [right, n-1]$ 中，满足
arr[i] <= arr[j]且使删除长度 $j - i - 1$ 最小的配对。直接双重循环仍是 $O(n^2)$。第二个观察带来双指针：
arr[0..left]与arr[right..n-1]都是非递减的，于是「对固定的 $i$，最小的可行 $j$」随 $i$ 增大而单调不减——$i$ 变大意味着arr[i]变大（或持平），要求的 $j$ 只会更靠右。单调性成立，就可以让两个指针各自单向前进，总步数 $O(n)$。双指针的不变量是：$i$ 从 $0$ 出发只增，$j$ 从
right出发只增；每当arr[i] <= arr[j]时，当前的 $j$ 就是配得上这个 $i$ 的最小可行右端点，此时删除长度 $j - i - 1$ 是该 $i$ 的最优值，记入答案后把 $i$ 推进一格；否则arr[i]太大，只能把 $j$ 右移去找更大的值。因为 $j$ 从不回退，所以每个 $i$ 被处理时 $j$ 恰好停在它的最小可行位置。三类方案取最小值即为答案。
解题步骤
- 先从左往右扩出最长非递减前缀的末位
left：只要arr[left] <= arr[left+1]就继续右移。循环条件里带left + 1 < n防止越界。- 若
left == n - 1直接返回 $0$。这说明整个数组已经非递减，删空段即可。这个提前返回还有一层作用：保证后续right的计算不会与left产生退化交叠。- 再从右往左扩出最长非递减后缀的首位
right：只要arr[right-1] <= arr[right]就继续左移。同样带right > 0防越界。- 先用两个「只保留一侧」的方案初始化答案：
res = min(n - left - 1, right)。前者是删掉前缀之后的全部，后者是删掉后缀之前的全部。这两种必须单独算，因为双指针循环里 $i$ 和 $j$ 都必须落在有效范围内，无法表达「一侧完全不保留」。- 双指针从
i = 0、j = right出发，循环条件i <= left && j < n。$i$ 的上界是left而非 $n$，因为超出最长非递减前缀后，保留的前缀自身就不有序了；$j$ 的下界是right，理由对称。- 若
arr[i] <= arr[j]，用j - i - 1更新答案并i++。删除区间是 $[i+1, j-1]$，长度正是 $j - i - 1$。此时该 $i$ 已找到最优 $j$，推进 $i$ 去处理下一个；不推进 $j$ 是因为更大的 $i$ 可能仍配得上这个 $j$，那样删得更少。- 否则
j++。arr[i] > arr[j]说明当前 $j$ 太小接不上，而 $j$ 左侧的更小，只能往右找。这一支不更新答案。- 返回
res。以
arr = [1, 2, 3, 10, 4, 2, 3, 5]走一遍：求前缀：$1 \le 2 \le 3 \le 10$，到下标 3 时 $10 > 4$ 停下，
left = 3。不等于 $n - 1 = 7$，继续。
求后缀：right初值 $7$；检查arr[6] = 3 <= arr[7] = 5成立，right = 6；检查arr[5] = 2 <= arr[6] = 3成立，right = 5；检查arr[4] = 4 <= arr[5] = 2不成立，停止。right = 5，最长非递减后缀是[2, 3, 5]。
初始答案：只留前缀要删 $8 - 3 - 1 = 4$ 个；只留后缀要删right = 5个。res = 4。
双指针：i = 0、j = 5。arr[0] = 1 <= arr[5] = 2，删除长度 $5 - 0 - 1 = 4$，res仍为 $4$，i = 1。
arr[1] = 2 <= arr[5] = 2（注意用 $\le$），删除长度 $5 - 1 - 1 = 3$，res = 3，i = 2。
arr[2] = 3 > arr[5] = 2，j = 6。
arr[2] = 3 <= arr[6] = 3，删除长度 $6 - 2 - 1 = 3$，res仍为 $3$，i = 3。
arr[3] = 10 > arr[6] = 3，j = 7。
arr[3] = 10 > arr[7] = 5，j = 8，循环因j < n失败退出。
返回 $3$，对应删掉[10, 4, 2]（下标 3 到 5），剩下[1, 2, 3, 5]。第二步那个
arr[1] = 2 <= arr[5] = 2尤其值得注意：若比较写成严格小于，这一档会被跳过，res停在 $4$，答案就错了——这正是「非递减允许相等」的直接体现。
代码实现
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)$。求最长非递减前缀与后缀各是一趟单向扫描；双指针阶段 $i$ 至多前进
left + 1步、$j$ 至多前进 $n - right$ 步，两者都不回退，合计不超过 $2n$ 次比较。全程没有排序也没有嵌套循环。- 空间复杂度：$O(1)$。只用了
left、right、res、i、j五个整型变量，不复制数组也不建辅助结构。
关键点总结
- 「删除一个连续段」等价于「保留一个前缀加一个后缀」，这个转换把二维的区间枚举降成了两端各选一个切点的问题，是本题的第一步也是最关键的一步。
- 可行解的范围往往能先被单调性夹住：保留的前缀必在最长非递减前缀之内、后缀必在最长非递减后缀之内。先把候选空间砍到线性，再考虑怎么配对。
- 两个有序序列上找满足
a[i] <= b[j]且间隔最小的配对，是相向/同向双指针的标准场景；成立的依据是「随着 $i$ 增大，最小可行 $j$ 单调不减」，这一条必须能证明，否则双指针不成立。- 「只保留一侧」的两种极端方案必须单独初始化答案，双指针的循环范围表达不了它们。凡是双指针题都要检查一遍端点情形是否被覆盖。
- 面试视角：面试官会依次问三件事——为什么答案一定是「前缀 + 后缀」的形态；为什么 $i$ 只需在最长非递减前缀内枚举；双指针的移动依据是什么（
arr[i] > arr[j]时为什么只能移 $j$）。如果被追问优化前的思路，可以说「对每个 $i$ 在后缀上二分找第一个不小于arr[i]的位置」，那是 $O(n \log n)$ 的自然过渡版本，双指针是它的线性化。
易错点总结
- 比较写成严格小于：
arr = [1, 2, 3, 10, 4, 2, 3, 5]中arr[1] = 2与arr[5] = 2相等的那次匹配会被跳过，返回 $4$，正确答案是 $3$。- 把
left当成前缀长度而不是末位下标：arr = [1, 2, 3, 10, 4]中left = 3表示下标，若按长度理解写成n - left，只留前缀的方案会算成 $2$ 而非 $1$，最终返回值偏大。- 答案初始化只取
n - left - 1而漏掉right：arr = [5, 4, 3, 2, 1]时left = 0、right = 4，只保留前缀要删 $4$ 个、只保留后缀也要删 $4$ 个，漏掉一侧会在类似arr = [10, 1, 2, 3]的用例上返回 $3$ 而非 $1$。- 双指针里
arr[i] > arr[j]时移动 $i$：arr = [1, 2, 3, 10, 4, 2, 3, 5]中i = 2、j = 5处 $3 > 2$，若移 $i$ 会跳过下标 2 这个本可与下标 6 配对的位置，最终返回值偏大。- 匹配成功后同时推进 $i$ 和 $j$：会漏掉「更大的 $i$ 配同一个 $j$」这类更优解，
arr = [1, 1, 1, 5, 2]上会返回比最优值更大的删除长度。- 删除长度写成
j - i：arr = [1, 2, 3, 10, 4, 2, 3, 5]中最优那次会算成 $4$ 而非 $3$，因为删的是开区间 $(i, j)$ 内的元素，长度是 $j - i - 1$。- $i$ 的循环上界写成
i < n：i越过left后前缀自身已不非递减，arr = [1, 2, 3, 10, 4]中i = 4会与某个 $j$ 配对并给出一个非法方案，返回值偏小。- 求
right时循环条件漏掉right > 0：arr = [1, 2, 3]若没有提前返回，right会一直左移到 $-1$ 并访问arr[-1]越界。- 求
left时用arr[left] < arr[left + 1]：arr = [1, 1, 1, 2]会在第一步就停下，left = 0，把本已有序的数组判成需要删除 $3$ 个元素，正确答案是 $0$。- 认为答案可能是 $n$：
arr = [5, 4, 3, 2, 1]时至少可以只保留一个元素，删 $4$ 个即可，返回 $5$ 说明把「保留空数组」当成了唯一出路。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 581. 最短无序连续子数组 | 中等 | 求最短的「排序后即整体有序」的段，靠前后缀极值夹逼而非删除拼接 |
| 665. 非递减数列 | 中等 | 允许修改一个元素使数组非递减，考的是在拐点处改左还是改右的贪心 |
| 209. 长度最小的子数组 | 中等 | 同向双指针求最短合法窗口，但窗口是被保留的对象且判据是和 |
| 26. 删除有序数组中的重复项 | 简单 | 原地删除的双指针写法，删除的是分散元素而非连续段 |
| 167. 两数之和 II - 输入有序数组 | 中等 | 有序数组上双指针配对的最简形态，移动依据同为「当前和偏大还是偏小」 |
| 300. 最长递增子序列 | 中等 | 允许删除任意多个不连续元素，问题从两端切点变成子序列 DP 或贪心加二分 |
| 80. 删除有序数组中的重复项 II | 中等 | 快慢指针原地保留，判据是与前第二个保留元素比较，考的是双指针的语义设计 |
| 11. 盛最多水的容器 | 中等 | 相向双指针，移动依据来自「短板不可能更优」的反证而非有序性 |