题目描述
思路解析动画文字版
记牢:剩下的一定是前缀加后缀。先求最长非递减前缀末尾 i、后缀起点 j;保底取 min(n-i-1, j);再双指针归并,arr[l] ≤ arr[r] 可拼、删 r-l-1 并 l 右移,接不上就 r 右移。
总览 · 删最短的中间一段：先看清画面。上面这排格子是 arr = 1,2,3,10,4,2,3,5,一共 8 个数。我们要删掉中间连续的一段,让剩下的从左到右非递减,并且删的这段越短越好。右边面板记三件事:非递减前缀到哪结束、非递减后缀从哪开始、目前找到的最短删除长度,现在都还没定。我们分两步先把前缀和后缀框出来。
找前缀 · 第 0 个数自成一段：先从左往右找最长的非递减前缀。第 0 个数 1 自己就是一段合法的非递减序列,标成绿色,绿色代表「保留下来的前缀」。接着我们一个个往右看,只要后一个不小于前一个,前缀就能继续延伸。
找前缀 · 1 ≤ 2 延伸：看下标 1 的 2,它和前一个 1 比,1 不大于 2,非递减没断,前缀往右长一格,现在是 1,2。绿色段也跟着多盖一格。继续往后看。
找前缀 · 2 ≤ 3 延伸：下标 2 的 3,和前一个 2 比,2 不大于 3,还在非递减,前缀延伸到 1,2,3。一路绿到下标 2。再看下一个。
找前缀 · 3 ≤ 10 延伸：下标 3 的 10,和前一个 3 比,3 不大于 10,非递减依然成立,前缀延伸到 1,2,3,10。这个 10 暂时被收进前缀,但它会不会成为麻烦,接着看。
找前缀 · 10 大于 4 断开：到下标 4 的 4,和前一个 10 比,10 比 4 大,非递减在这里断了,标红提醒。所以最长非递减前缀就到下标 3 结束,记 i 等于 3,前缀是 1,2,3,10。前缀框定,接下来换个方向找后缀。
找后缀 · 第 7 个数自成一段：现在从右往左找最长的非递减后缀。最右边下标 7 的 5 自成一段,标成蓝色,蓝色代表「保留下来的后缀」。我们往左走,只要前一个不大于后一个,后缀就能往左延伸。
找后缀 · 3 ≤ 5 延伸：看下标 6 的 3,它的后一个是 5,3 不大于 5,非递减成立,后缀往左长到 3,5。蓝色段往左多盖一格。继续往左看。
找后缀 · 2 ≤ 3 延伸：下标 5 的 2,后一个是 3,2 不大于 3,还在非递减,后缀延伸到 2,3,5。蓝色盖到下标 5。再往左看一个。
找后缀 · 4 大于 2 断开：到下标 4 的 4,它的后一个是 2,4 比 2 大,非递减断开,标红。所以最长非递减后缀从下标 5 开始,记 j 等于 5,后缀是 2,3,5。现在前缀末尾 i 是 3、后缀起点 j 是 5,i 小于 j,说明中间确实有东西要删。
保底方案一 · 只留前缀：动手归并之前,先准备两个保底答案。第一手:干脆只保留前缀 1,2,3,10,把后面 arr 下标 4 到 7 这一整段灰掉删掉,长度是 n 减 i 减 1,也就是 8 减 3 减 1 等于 4。这是一定可行的删法,先记下候选 4。
保底方案二 · 只留后缀：第二手:只保留后缀 2,3,5,把前面 arr 下标 0 到 4 灰掉删掉,长度就是 j 等于 5。这一手要删 5 个,比第一手差。两个保底取小,min(4,5) 等于 4,所以当前最短删除先定成 4。下面看双指针能不能把它压得更短。
双指针归并 · 摆好两个指针：关键一步来了。我们想保留更多两端、删更少中间。摆两个指针:l 从前缀的头部下标 0 出发,r 从后缀的头部下标 5 出发。思路是,保留前缀的 0 到 l 这一段,接上后缀的 r 到末尾这一段,只要接缝处不降,中间的 l 加 1 到 r 减 1 就是要删的部分,长度 r 减 l 减 1。开始归并。
比一比 · l=0,r=5：第一次比较。l 在下标 0 值是 1,r 在下标 5 值是 2,1 不大于 2,接缝成立。保留前缀到下标 0,也就是 1,接上后缀 2,3,5,中间删 arr 下标 1 到 4,长度 r 减 l 减 1 等于 4。和保底一样,没变短。我们让 l 右移,尝试多保留一点前缀。
比一比 · l=1,r=5：第二次比较。l 走到下标 1 值是 2,r 还在下标 5 值是 2,2 不大于 2,接缝成立。保留前缀 1,2,接上后缀 2,3,5,中间删 arr 下标 2 到 4,也就是 3,10,4,长度等于 3。比 4 更短,最短删除刷新成 3。l 继续右移。
比一比 · l=2,r=5：第三次比较。l 在下标 2 值是 3,r 在下标 5 值是 2,这回 3 比 2 大,接缝降下来了,拼不上。问题出在后缀头那个 2 太小,没法接在 3 后面。办法是把 r 右移,等于把后缀头的 2 也删掉,换个更大的数来接。
比一比 · l=2,r=6：第四次比较。r 右移到下标 6 值是 3,l 还在下标 2 值是 3,3 不大于 3,接缝成立,非递减允许相等。保留前缀 1,2,3,接上后缀 3,5,中间删 arr 下标 3 到 5,长度等于 3,和当前最短一样。l 再右移。
比一比 · l=3,r=6：第五次比较。l 走到下标 3 值是 10,r 在下标 6 值是 3,10 比 3 大,接不上。前缀尾巴这个 10 太大了,后缀里得找个不小于 10 的数才能接。继续把 r 右移试试。
比一比 · l=3,r=7：第六次比较。r 右移到下标 7 值是 5,l 还在下标 3 值是 10,10 比 5 大,还是接不上。后缀里再没有更大的数了,r 走到末尾外面,归并到此结束。那个 10 注定保不住,必须被删。
揭晓 · 删掉中间 3 个数：把归并里最短的那次删法摆出来。保留前缀 1,2,接上后缀 2,3,5,删掉中间灰色的 3,10,4 这三个数,剩下的 1,2,2,3,5 从左到右完全非递减。删 10,4,2 那一种也是删 3 个、剩 1,2,3,3,5,同样成立,两种都对、长度都是 3。
完成 · 最短删除长度 = 3：收个尾。整道题先用一次左右扫描框出最长非递减前缀和后缀,再用双指针归并在接缝处贪心地保留尽量多两端、删尽量少中间。arr = 1,2,3,10,4,2,3,5 最终最短删除长度是 3。两个指针都只往前走,线性时间、常数额外空间,既快又省。
边界:本就有序返回 0(可删空段);严格递减只能留一个、删 n-1 个,靠保底给出;单元素返回 0。
面试重点:删连续段所以剩余必是前缀加后缀;前缀尾可能大于后缀头、需双指针在接缝处取舍而非直接拼;双指针靠 l、r 各单调右移做到 O(n),与参考代码二分版 O(n log n) 等价同解。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def findLengthOfShortestSubarray(self, arr: List[int]) -> int: n = len(arr) i, j = 0, n - 1 while i + 1 < n and arr[i] <= arr[i + 1]: i += 1 while j - 1 >= 0 and arr[j - 1] <= arr[j]: j -= 1 if i >= j: return 0 ans = min(n - i - 1, j) for l in range(i + 1): r = bisect_left(arr, arr[l], lo=j) ans = min(ans, r - l - 1) return ans复杂度
- 时间：O(n log n)，n 是数组长度。求前缀、求后缀各扫一遍是 O(n);参考代码对前缀里最多 n 个元素,每个都在后缀里做一次二分查找,每次 O(log n),合起来 O(n log n),这是代码区展示的写法的复杂度。动画演示的双指针归并写法,l 和 r 都只往前走、各最多 n 步,可以把找候选这步降到 O(n),整体 O(n)。两者答案一致
- 空间：O(1)，按峰值算。除了输入数组,只用了 i、j、ans、l、r 这几个下标和一个答案变量,都是常数个,不随 n 增长。无论二分版还是双指针版,都没有额外开数组或拷贝,所以额外空间是常数 O(1)
易错点
面试追问把动画讲成自己的话
追问为什么删完剩下的一定是「前缀加后缀」的形式?
追问找到最长前缀和后缀后,为什么不能直接把它们拼起来,还要双指针归并?
追问双指针版为什么是 O(n),它和参考代码的二分版什么关系?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
袋子里最少数目的球
LeetCode 1760 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题