二分答案+贪心：LeetCode 3824题最小K值问题全解析

双周赛Q2这个位置拼的往往不是思路有多惊艳而是能不能在十分钟之内把题面翻译成一个通用模板。第175场的3824题表面说的是减小数组使其满足条件的最小K值实际上就是把一个单调性判断问题藏在了几个条件背后给你一个数组每个位置最多能削掉K问最小的K是多少才能让整个数组变成我们想要的样子。这种题在双周赛里出现频率很高解法也很固定——先看出单调性再套二分答案最后在check函数里用贪心扫一遍。这篇文章把完整的思考链路和落地细节拆开讲包括二分边界的选取、check函数为什么能线性扫描、以及赛场上容易被卡住的几个隐蔽坑点希望能帮你在下次遇到同类题时省下试错时间。1. 把题意翻译成二分模型1.1 为什么想到二分答案先说我个人的习惯拿到一道求最小值的题如果题目还带一个明显的可行性判断我第一反应就是二分。因为求最小K本质上是在一个有序的整数区间里找一个临界点而临界点的判定规则往往比直接构造最优解简单得多。具体到这道题它的核心操作是每个元素最多减少K——注意是最多减少不是必须减少。这意味着K越大我们调整数组的自由度就越大越容易满足题设条件K越小能动的范围就越窄越容易失败。这是一个非常干净的单调关系如果K5能完成任务那么K6、K10一定也能反之如果K5完不成那么K4、K3更不可能。单调性齐了二分答案的框架就成立。很多新手看到求最小K就想着直接构造答案但这类题的K取值范围可能很大。假如数组长度是10^5元素值范围到10^9你根本不可能逐K枚举而二分的总轮数只要约30次哪怕每次check是O(n)整体也就是10^7级别完全可控。1.2 还原一个可执行的判断条件题面里满足条件这四个字是灵魂不同版本可能对应不同具体条件。第175场这道题在我看到的常见版本中条件可以理解成经过若干次单点减少不超过K的操作后数组要变成非递增序列即满足a[0] a[1] a[2] ... a[n-1]注意这里有一个隐藏信息操作只允许减少不允许增加。所以如果某个位置的值比后一个位置小我们是不能把后一个位置强行拉高的只能把前面这个或后面那个往下压。这也决定了解题的走向整个调整过程一定是从左往右把逆序削平而不是想着去补某个元素。判断某个K是否可行时我们不需要真的把所有操作都模拟出来只需要看一个简化问题从左往右扫手里的当前上限cur能不能一路扛住后面的每个元素。如果每个位置都能通过最多削减K的代价满足 cur 下一个值那么这个K就是可行的。2. check函数为什么可以贪心扫一遍2.1 从左往右维护当前上限check(K) 的具体写法是这道题最核心的部分。我习惯维护一个变量cur代表当前扫描位置已经处理完的那个元素值。初始时cur a[0]因为第一个元素不用管左侧约束保持原值就是最优。然后从i 1开始往右扫描如果 a[i] cur说明当前元素本来就不超过左侧需求不需要做任何操作直接把cur更新为a[i]。如果 a[i] cur说明这里出现了一个高峰必须把a[i]通过减少操作压到不超过cur的位置。为了尽量少消耗K我们把a[i]压到刚好等于cur需要的减少量是 d a[i] - cur。如果 d K说明一次操作的上限不够直接返回false如果 d K就把cur维持不变继续往后走。这段逻辑写成代码非常短但里面藏着一个关键问题为什么遇到高峰时要把a[i]压到刚好等于cur而不是压到比cur更小的某个值原因很简单对后面的元素来说cur越小后面的约束就越严格。比如cur10时后面元素只要不超过10就行如果我把a[i]压到5那么后面所有元素都被迫不能超过5很可能导致原本可行的情况变得不可行。所以压到刚好等于cur才是收益最大的选择既满足了当前相邻关系又给后面留了尽可能大的余量。2.2 局部最优为什么就是全局最优很多人第一次看这个贪心会觉得不放心担心当前压一点点后面会不会反而需要压更多。我们分析一下就能发现这个贪心的决策实际上没有引入任何额外代价。当我们把a[i]压到cur时只改变了一个事实a[i]从原来的大值变成了cur。这个改变让a[i]满足 a[i] cur也就是解决了当前这一对相邻元素的次序问题。同时这个改变对后面所有元素的影响都只是需要满足的上限从原来的大值变成了cur或更小。如果cur本身已经足够大后面可能完全不受影响如果cur很小那么即使让a[i]保持原值后面也一样要被压到不超过cur因为a[i]这个位置已经是一个山脊它决定了后续的通行高度。所以从左往右扫一遍每一步都只做必要的最小削减得到的就是在固定K下最节约的调整方案。这个方案如果失败那么任何其他方案都不可能成功因为其他方案只会让某些位置的cur变得更小或者让某个位置浪费更多削减额度。2.3 一条边界原数组本身合法时K0这里必须单独提一个边界情况如果原始数组已经满足非递增条件那么答案就是0因为根本不需要操作。这种情况在二分里天然会被覆盖check(0)会从左往右扫一遍发现所有位置都满足 a[i] cur最终返回true所以二分答案会在0处结束。但我见过不少同学在初始化二分右边界时把右边界设成0或者把ans的初始值写成-1然后判断如果原数组合法就返回0这些其实都是多余的操作只要二分模板写对了0会自动被包含在解空间里。不过有一点要注意如果原题允许不操作之外还额外要求至少操作一次那题意就变了这属于另一种特殊情况需要在读题时做区分。就我看到的版本而言K0是合法答案。3. 代码落地与二分细节3.1 C 实现下面给出一个完整可跑的C版本。这个版本没有用额外的数组拷贝直接在原数组上做逻辑判断check函数的参数K是传值进来的遍历时不会修改原数组所以多次调用也安全。class Solution { public: bool check(const vectorint a, long long K) { int n a.size(); long long cur a[0]; for (int i 1; i n; i) { if (a[i] cur) { long long d (long long)a[i] - cur; if (d K) return false; // 压平后cur保持不变 } else { cur a[i]; } } return true; } int minimumK(vectorint a) { int n a.size(); if (n 1) return 0; long long l 0, r 0; for (int x : a) r max(r, (long long)x); // 右边界可以取数组最大值因为把每个元素都削到0一定可行 while (l r) { long long mid (l r) / 2; if (check(a, mid)) r mid; else l mid 1; } return (int)l; } };这里有三个细节值得展开。第一个是右边界。上面我取的是数组最大值因为只要K足够大到能把任何一个元素直接削成0那么把整个数组都削成0数组一定是非递增的全是0。所以右边界取max就够了。有的同学会写成 max - min其实也行但取max更省事且不会漏解。注意如果所有元素都是负数那么最大值也可能是负数右边界就要做相应调整但从比赛题的常规数据范围来看非负整数数组是主流所以取max通常够用。第二个是溢出的问题。K的取值范围可能到10^9mid的计算用l r可能导致溢出所以mid要写在 long long 的上下文里。check函数内部的d计算也一样用long long承接是稳妥习惯。第三个是二分循环体的写法。这里用的是常见的左闭右开变种l 0, r maxVal 1 也行但上面代码里用的其实是左闭右闭的写法while (l r)mid (l r) / 2如果check(mid)为true则r mid否则l mid 1。这种写法的终止条件是l r最终答案就是l。如果你更喜欢左闭右开可以把r初始化成maxVal 1同样正确但要注意check(mid)里mid是一个真正可用的K不是二分猜测的答案加1。3.2 Java / Python 版本要点Java版本和C几乎一致只需要注意数组访问和类型转换。核心check函数如下private boolean check(int[] a, long K) { long cur a[0]; for (int i 1; i a.length; i) { if (a[i] cur) { long d (long) a[i] - cur; if (d K) return false; } else { cur a[i]; } } return true; }Python版本更简洁但要注意Python的整除是向下取整对非负整数没影响另外Python的int是任意精度不太担心溢出反而要在二分边界上小心别把右边界设置成无穷大。def check(a, K): cur a[0] for x in a[1:]: if x cur: if x - cur K: return False else: cur x return True def minimumK(a): if len(a) 1: return 0 l, r 0, max(a) while l r: mid (l r) // 2 if check(a, mid): r mid else: l mid 1 return lPython版本最大的坑其实是性能。check函数里的for循环在Python身上比C慢得多但好在二分次数只有大约30次每次O(n)n在10^5量级时完全没问题。如果你用的是PyPy速度会更好。不过如果是极端数据n10^6Python的O(n log M)就可能有点吃力这时可以考虑优化成O(n)的贪心直接算答案——后面我会提这个扩展思路。3.3 数组方法使用中的几个坑既然热词里有很多关于数组方法的搜索这里提几个和本题相关的实战经验。第一如果你在JavaScript里用reduce或者forEach去写check注意不要在回调里直接改原数组。很多人在check内部写a[i] cur去模拟削减结果下一次check调用时数组已经被改过了整个二分逻辑全乱。正确做法是只读数组用局部变量维护cur或者每次check前做一次数组拷贝。拷贝的成本是O(n)二分30次后就是O(30n)其实也扛得住但没这个必要。第二C里把vectorint a作为参数传值时会发生一次完整拷贝。如果check函数每次都被调用这个拷贝成本会累积到O(n log M)表面看复杂度没变常数却翻倍了。所以check参数应该写成const vectorint。第三数组索引的问题。有的同学喜欢在check里从右往左扫或者在循环里同时访问i和i-1这时候一定要小心边界。左到右扫描时i从1开始就不会访问到a[-1]右到左扫描时i要从n-2开始否则越界是家常便饭。这道题用左到右扫描天然避开了越界。4. 现场踩坑与调试记录4.1 常见WA原因和对应排查这个题目虽然框架固定但细节上翻车的地方不少。我把赛场上常见的问题整理成一个速查表遇到WA可以直接对照排查。症状可能原因解决办法小数据能过大数据超时check里拷贝了数组改成const引用/只读数组答案总是比预期大1二分右边界开小了导致真正可行的大K被排除右边界改成max(a)或者max(a)1答案总是0但实际需要操作check里把cur更新错了遇到a[i] cur时没处理检查是否漏了d K的判假逻辑数组有负数时答案不对右边界从0开始但数组最小值小于0右边界取max(a)不要假设非负原数组合法但返回1二分初始化l1而不是l0左边界必须从0开始极端场景n1返回异常没有特判单元素数组n1直接返回0这里重点说一下原数组合法但返回1这个问题。如果你把二分的左边界设成1那就默认K至少为1但题目允许K0结果就是答案被整体抬高了1。这种错误在比赛中特别隐蔽因为样例通常不会设计成原数组恰好合法的情况。我自己的习惯是所有求最小值、且0可能合法的题左边界一律从0开始如果题目明确说K必须是正整数再从1开始。另一个容易踩的是check函数里cur的更新位置。有些同学会写成这样for (int i 1; i n; i) { if (a[i] cur) { if (a[i] - cur K) return false; cur a[i]; // 错误这里应该保持cur不变 } else { cur a[i]; } }这个错误一眼看上去很荒谬但实际比赛里紧张起来真有人会写错。如果遇到高峰并把a[i]压平到cur那么cur应该保持原值因为数组已经被压平了后面要比较的对象仍然是之前那个cur如果你把cur更新成a[i]这个未削减的原始大值那就相当于什么都没压后面会误判。为了完全避开这个问题可以把压平后的逻辑统一成cur min(cur, a[i])但这样就要多一次min运算效率上差别不大。我更推荐直接写分支逻辑清楚。4.2 复杂度与稳定性分析这道题的时间复杂度是O(n log M)其中M是二分的范围。如果右边界取max(a)M最多是10^9或题目允许的更大值log2(10^9)只有约30所以整个复杂度大约是O(30n)。空间复杂度是O(1)因为check函数只用了常数个变量。但这里有一个可以继续优化的方向如果你发现题目的数据范围特别大比如n10^6、M10^18那么O(n log M)大概在3x10^7这个量级C可以稳过Python可能悬。这时候可以把二分改成一次线性扫描直接求答案从左往右维护cur记录所有高峰的峰值与左侧cur之间的最大差值这个最大差值就是最小K。本质上就是check函数里所有失败点中的最大d值。def minimumK_linear(a): if len(a) 1: return 0 ans 0 cur a[0] for x in a[1:]: if x cur: ans max(ans, x - cur) else: cur x return ans这个线性版本其实就是贪心的直接体现我们不需要二分试探因为每次遇到高峰期需要削掉的量是确定的取所有高峰期里最大的削减量即可。为什么这样是对的因为check(K)的失败条件就是某个位置需要削减的量超过K所以让所有削减量都满足的最小K恰好是这些削减量中的最大值。不过话说回来如果原题的满足条件不是非递增而是更复杂的约束这个线性优化就不能轻易套用二分反而是更通用的模板。4.3 题目变体的扩展思路这类减小数组使其满足条件的最小K值的题目变体非常多。比如把目标从非递增改成相邻元素的差不超过target那么check函数里的判断条件就要相应调整假设要求 |a[i] - a[i-1]| target从左往右扫时如果当前元素太高需要压到 cur target如果当前元素太低反而需要看能不能把前面的某个元素压下来这时单纯从左往右贪心可能就不够了可能需要从两个方向做预处理。另一个常见的变体是每个位置只能操作一次这其实已经隐含在最多减少K里了因为操作一次减少1和操作一次减少K本质上都算一次操作并没有限制操作次数但如果题目改成总共只能操作m次那么二分答案就不再是唯一解法可能需要结合优先队列做反悔贪心。还有一类题目会把减小换成增加那思考方向就完全反过来了。不过核心方法论是通用的第一步判断可行性是否随K单调第二步设计check函数第三步处理二分边界。掌握这三板斧这类题不管怎么变形都能很快找到切入点。5. 写在最后的实战心得如果你在赛场上遇到这类题我建议按这样的顺序来先花30秒判断答案是最小K还是最少操作次数这决定了思路方向然后手推一两个例子验证单调性不要直接写代码如果确认是二分答案就先把check函数写对再去套二分模板因为check函数才是整道题的地基。另外有一个小技巧在本地调试时可以针对几个特殊用例测试包括原数组已经非递增、所有元素全部相等、只有一个元素、数组是严格递降的、数组中间有一个巨大峰值。这些用例基本能覆盖所有边界情况。原数组已经非递增时答案应该是0这是最容易被忽略的边界严格递降时答案也是0因为根本不用动中间有巨大峰值时答案往往是峰值减去左侧最近的一个低谷可以手算验证check函数的正确性。从双周赛的难度分布来看Q2通常不会考太复杂的算法但非常考验选手能不能快速识别题型。如果你能把最小K值 - 单调性 - 二分答案 - 贪心判定这条链路练成本能反应这类题基本就是送分题。真正拉开差距的不是会不会写二分而是能不能在紧张的状态下把check里的细节一次写对不给自己留调试的余地。