昨天刚打完第 486 场 LeetCode 周赛Q1 是一道看上去人畜无害的数组题题目编号 100971名字叫《移除前缀使数组严格递增》。我当时的第一个念头是这题不就是找第一个破坏递增的位置然后删掉吗结果本地一跑样例就发现不对评论区也有不少人在问为什么直接扫第一个逆序对会报错。这篇文章就把这道题的完整推理、代码实现、边界用例以及我在周赛现场踩过的坑重新捋一遍。题目本身不难但它把“数组”“前缀”“严格递增”这三个最基础的概念组合在一起非常典型地考验你有没有真正理解删除操作对相邻关系的影响。如果你是刚开始刷题、周赛想稳定拿到 Q1、或者面试前想复习单调性相关套路这篇都值得细读。全文不会只给结论我会把从暴力到 O(n) 的思考过程完整走一遍顺便聊聊这类题在周赛里最常见的几个误区。1. 先把题目翻译成人话到底让我们做什么1.1 一句话读懂题意题目名称已经说明了一切给定一个整数数组你可以从头开始删除一段连续的元素这段可以一个都不删要求剩下那部分数组严格递增最后输出最少需要删除多少个前缀元素。这里有两个关键词必须先搞清楚。“前缀”指的是从数组最左边开始的一段连续子数组你只能删开头不能从中间挖掉一块也不能从结尾往前删。“严格递增”指的是任意相邻位置都要满足左边严格小于右边比如[1,2,2]就不算严格递增因为2 2不满足的条件。举个例子如果nums [1, 2, 3]数组本身已经严格递增答案就是 0一个都不删。如果nums [1, 2, 1]删掉[1, 2]之后剩下[1]单元素数组一定是严格递增的所以答案是 2。最极端的情况是[5, 4, 3, 2, 1]不管怎么删前半段只要留下一个元素就满足条件所以答案是 4也就是把前 4 个全删掉。1.2 为什么检查相邻元素就够用了有些刚入门的朋友会问严格递增不是说整个数组任意两个位置都要满足nums[i] nums[j]吗只看相邻位置够不够答案是够的。因为递增关系具有传递性如果nums[0] nums[1]、nums[1] nums[2]那自然就有nums[0] nums[2]。所以只要所有相邻位置都满足严格小于整个数组就一定严格递增。反过来也一样只要有一处相邻位置不满足整个数组就不满足严格递增。这个性质很关键它把“全局判断”压缩成了“相邻对判断”这也是下面所有解法的出发点。1.3 先写一个暴力版本给后面的优化当基准最开始没必要直接追求最优解先写一个能保证正确的暴力版本。思路非常直白枚举删除前缀的长度k从最小的k开始试每试一个就检查剩余部分是否严格递增一旦找到合法就返回。def min_remove_brute(nums): n len(nums) for k in range(n): # 尝试删除前 k 个元素 ok True for i in range(k, n - 1): # 检查剩余数组的相邻关系 if nums[i] nums[i 1]: ok False break if ok: return k return n - 1 # 理论上到不了这里留一个元素总行这个暴力版本在数据量小的时候完全没问题时间复杂度是 O(n²)。但如果n到了 10^5 级别枚举一次再检查一次就是 10^10 次操作铁定超时。所以我们得找到能够一次扫描解决的规律。2. 核心洞察答案由“最后一个逆序对”决定2.1 把破坏递增的相邻位置标记为“坏点”为了讨论方便我给这题引入一个称呼如果一个相邻对满足nums[i] nums[i1]那我们就说下标i是一个“坏点”。一个数组严格递增等价于坏点集合为空。来看一个具体例子nums [1, 3, 2, 4, 1, 5]。逐对检查i 01 3好点i 13 2坏点i 22 4好点i 34 1坏点i 41 5好点所以坏点集合是{1, 3}。只要剩余数组里还包含下标1和2这两个元素它们就还会相邻就还会破坏递增性。这个视角可以帮我们脱离“整个数组”的束缚把问题聚焦到一个个独立的“冲突对”上。2.2 删除前缀的本质是让起点右移假设删除前缀长度是k那么剩余数组就是原来的nums[k], nums[k1], ..., nums[n-1]。我们可以把删除前缀理解成“把数组的起点从下标 0 往右移到下标 k”。原来下标为i的元素在剩余数组里变成了下标i - k。那么一个坏点i会不会继续破坏递增性就取决于i是否被删掉了如果i k说明坏点对(i, i1)里的两个元素都被删了问题彻底消失如果i k说明nums[i]和nums[i1]仍然在剩余数组里而且仍然相邻这个冲突对会原样保留下来。这里有个很容易想当然的点删除的是前缀删掉前面的元素不会改变后面元素的相邻关系。nums[i]和nums[i1]只要都留下它们永远是邻居之前是什么关系现在还是什么关系。2.3 反直觉的地方不是第一个坏点而是最后一个坏点很多人的第一反应是找到第一个坏点把它连同前面的元素全删掉不就完事了吗我用一个反例来说明这不行nums [1, 2, 2, 3, 2, 4]。坏点有i 1因为2 2和i 3因为3 2。如果只处理第一个坏点删除长度取 2剩下的是[2, 3, 2, 4]。这时候2 2已经不存在了但3 2还在依然不严格递增。问题就出在这里第一个坏点被覆盖以后起点确实向右移了但如果后面还存在别的坏点它同样会被原封不动地带进剩余数组。所以正确的处理方式不是看第一个坏点而是看最后一个坏点。删除长度必须大于等于“最大坏点下标 1”才能保证所有坏点对都被整个删掉。用生活里的例子类比坏点就像一条路上的关卡你要从所有关卡右侧重新开始走。只解决第一个关卡就停下来后面照样有关卡堵着你只有把起点挪到最后一个关卡右边整段路才畅通。2.4 严格证明最少的合法删除长度就是 max_bad 1设max_bad是所有坏点下标里最大的那个。如果坏点集合为空数组本来就严格递增答案直接是 0。如果存在坏点那么我断言最小删除长度就是max_bad 1。先证明必要性如果删除长度k max_bad那么坏点max_bad还留在剩余数组里因为max_bad k它和nums[max_bad 1]仍然相邻仍然破坏严格递增。所以任何k max_bad的方案都不合法。再证明充分性取k max_bad 1剩余数组的所有相邻对下标都满足i k max_bad。既然max_bad是最大的坏点那么所有下标大于max_bad的位置都不是坏点也就是所有相邻对都满足nums[i] nums[i1]。于是剩余数组严格递增。两条一夹结论就出来了答案等于最大坏点下标加一。如果完全没有坏点答案就是 0。3. 代码实现一个 for 循环解决但别被边界坑到3.1 参考代码这个结论写起来非常短核心就是一趟扫描找最大坏点。def min_remove_prefix(nums): n len(nums) max_bad -1 for i in range(n - 1): if nums[i] nums[i 1]: max_bad i return max_bad 1初始化max_bad -1的原因很简单如果数组完全严格递增最后max_bad保持-1-1 1 0正好对应“不需要删除”。这个初始值同时帮我们处理了单元素数组的情况——单元素数组没有相邻对当然严格递增答案 0。C 写法几乎一模一样class Solution { public: int minimumRemoval(vectorint nums) { int n nums.size(); int maxBad -1; for (int i 0; i 1 n; i) { if (nums[i] nums[i 1]) { maxBad i; } } return maxBad 1; } };Java 版本class Solution { public int minimumRemoval(int[] nums) { int n nums.length; int maxBad -1; for (int i 0; i 1 n; i) { if (nums[i] nums[i 1]) { maxBad i; } } return maxBad 1; } }3.2 边界用例跑一遍我自己写代码有个习惯例子越刁钻越好。下面这组数据可以拿去直接验证输入数组坏点集合答案删除后剩余数组[1,2,3,4]无0[1,2,3,4][1,2,1]{1}2[1][5,4,3,2,1]{0,1,2,3}4[1][1,1,1]{0,1}2[1][1,2,2,3,2,4]{1,3}4[2,4][1,2,3,1,2]{2}3[1,2]特别留意[5,4,3,2,1]这种完全递减的数组答案是n-1删除到只剩最后一个元素才严格递增。这也说明了一个事实任何长度大于 0 的数组删成单元素后一定严格递增所以这题一定有解不会出现“返回 -1”的情况。3.3 复杂度分析时间上只需要扫描一遍数组O(n)空间上只用了常数变量O(1)。这个复杂度已经是最优的因为不管怎样你至少要读一遍数组才能判断哪些位置破坏了递增性。有些同学会想能不能提前退出循环找到最后一个坏点就返回可以是可以但没必要。你反向从右往左扫找最后一个坏点可能提前退出但最坏情况还是 O(n)。正向扫一遍是最直观、最不容易写错的写法。4. 周赛实战为什么 Q1 也要多留个心眼4.1 我亲测翻车的完整过程比赛的时候我第一版代码写的其实是“找第一个坏点”具体就是从头扫遇到第一个nums[i] nums[i1]就返回i 1。当时觉得逻辑很完美破坏了删掉它和它前面的后面自然就好了。然后本地测试[1, 2, 2, 3, 2, 4]直接把我打醒了。按“第一个坏点”算出来答案是 2剩余[2, 3, 2, 4]肉眼可见3 2还横在那里。那一刻我才意识到问题出在“多个坏点”上于是改成记录最大坏点再用暴力对拍跑了几万组随机数据确认无误后才敢提交。这件事给我最大的教训是周赛 Q1 虽然难度不高但越是简单的题越容易用“直觉”跳过严谨推理。一个反例不够最好在脑子里过一遍“坏点到底有没有被删除操作覆盖掉”。4.2 这题最容易踩的坑按频率排个序第一类坑是把“删除前缀”和“删除任意一个元素”搞混。力扣上有一道经典题是“删除一个元素后判断数组是否严格递增”那是贪心 分类讨论的写法而“删除前缀”是完全不同的模型你只能动开头不能随便删中间。如果拿那道题的经验套这题肯定会乱。第二类坑是只盯第一个坏点忽略后面的坏点。这一点上面已经用反例演示过了而且这是评论区最常见的 WA 原因。第三类坑是忽略“前缀可以为空”。有些人会下意识把答案初始化为n或者弄一个while循环去找第一个破坏点最后在已经是严格递增的数组上多删了东西。记住严格递增数组的答案就是 0。第四类坑是处理单元素数组。n 1时没有相邻对严格递增天然成立答案应该是 0。别把循环写成for i in range(n)然后取nums[i1]那样会越界。4.3 周赛做题流程的小建议我在周赛里遇到这类数组题时一般按这个流程走先看数据范围。如果n很小暴力直接能过如果n到 10^5就要想 O(n) 或 O(n log n) 的解法。在草稿纸上把坏点标出来。这一步能避免很多“想当然”的错误。写代码前先想清楚删除操作到底会让哪些坏点消失写完代码后立刻用三组数据自测全递增数组、全递减数组、中间有多个坏点但第一个坏点很早出现的数组。这四步做完基本不用浪费时间在 WA 上。Q1 的定位就是签到题控制在 5 分钟内 AC 才是正常水平。5. 变形与进阶同一个知识点还能怎么考5.1 如果题目要求“返回剩余数组的最大长度”其实这就是同一个答案换个问法。最小删除长度是max_bad 1那么剩余数组的最大长度就是n - max_bad - 1。如果原数组本来就严格递增max_bad -1剩余长度就是n。比赛时如果遇到“求最长保留长度”的表述不要慌本质完全一样。5.2 如果把“前缀”换成“后缀”结论会怎样对称变化删除后缀nums[k1..n-1]保留nums[0..k]这时候要看的就不是最大坏点而是最小坏点。令min_bad为最小坏点下标。为了不让任何坏点对完整留在保留段里删除点k必须满足k min_bad。为了让删除的后缀尽量短就取k min_bad。所以最小删除后缀长度是n - 1 - min_bad。比如[1, 2, 1, 2]坏点是下标 1保留nums[0..1] [1,2]删掉后面两个元素剩余严格递增删除长度就是4 - 1 - 1 2。这和删除前缀的结论正好左右对称理解一个就能推出另一个。5.3 如果把“前缀”升级成“任意连续子数组”题目一旦变成“删除一段连续子数组使剩余部分严格递增求最大剩余长度”模型就完全不同了。因为你删除的区间左右两边会拼成新的相邻关系原来不是坏点的位置也可能因为拼接产生新的坏点。基本思路是预处理出前缀好段和后缀好段用pre[i]表示nums[0..i]是否严格递增用suf[i]表示nums[i..n-1]是否严格递增。然后枚举删除区间[l, r]满足pre[l-1]为真、suf[r1]为真并且衔接处nums[l-1] nums[r1]这样的删除方案才合法。这个问题的朴素枚举是 O(n²)但核心逻辑还是“坏点必须被删除区间覆盖”那一套只是多了一个衔接边界的判断。5.4 抽象出一种通用的竞赛思维从这道 Q1 出发我们可以提炼出一个很实用的思维模型遇到“通过删除恢复单调性”的问题永远先问自己——哪些冲突对必须被删除操作覆盖覆盖的方式决定了答案是看最大值还是最小值还是需要区间覆盖。比如删除前缀它只能从左边“越过”坏点所以要看最右边的坏点删除后缀从右边越过坏点所以要看最左边的坏点删除任意子数组则需要找到一个区间同时覆盖所有坏点并且额外检查拼接处。把这个框架搭起来以后题目再怎么变你都能快速定位到正确的思考方向。说个我自己的习惯遇到这种数组和“前缀”相关的题第一步永远是拿笔把坏点标出来再问自己删除操作到底会让哪些坏点消失。这个思维一旦成形类似题基本不会翻车。另外打完周赛别着急关页面拿暴力解法去和正解对拍十分钟比刷十道新题都管用。这道 Q1 就是个很好的例子——结论简单但和“第一个坏点”之间就差那么一层窗户纸。