贪心算法+堆+排序：LeetCode 2208与2406的最优解拆解

刷算法题这件事很多人觉得是“背模板”但真正到了LeetCode 2208和2406这两道题面前你会发现光背模板根本不够——一个考的是“数组和减半的最少操作次数”一个考的是“将区间分为最少组数”。两题看起来一个在折腾数组、一个在折腾区间但底层都是同一类思维贪心。我最初刷这两题时也想当然地写了暴力结果一个超时一个翻车后来才意识到它们之所以常被拿来当面试题是因为能迫使你在“局部最优”和“全局最优”之间做判断并且必须熟练使用堆和排序这两个基础武器。这篇文章我会把两道题一起拆开讲先从题意和考点入手再逐步推导为什么贪心成立接着给出可直接复现的Python实现最后聊聊差分数组这种替代思路和实战中容易踩的坑。无论你是刚刷数组/区间专题的新手还是准备面试想快速复盘的老手都能在这里找到一套“下次遇到同类题直接秒”的思考路径。1. 两题概览一个折腾数组一个折腾区间1.1 将数组和减半的最少操作次数2208题目给一个正整数数组nums每次操作可以选任意一个元素把它的值减半问最少操作多少次能让数组所有元素之和至少减少一半。举个例子nums [5, 19, 8, 1]数组和是33目标是至少减少到16.5也就是减少量达到16.5。如果第一次把19减半成9.5数组和变成23.5减少9.5第二次把9.5减半成4.75数组和变成18.75累计减少14.25第三次把8减半成4数组和变成14.75累计减少18.25这就算达标。三次操作就是答案。你可能会想为什么不第一次减8而是先减19这就是题目核心考点——每次操作选谁才能让操作次数最少。1.2 将区间分为最少组数2406题目给一个二维数组intervals每个元素形如[left, right]表示一个闭区间。现在要把所有区间分配到若干个组里同一个组内的任意两个区间不能重叠注意闭区间里端点重合也算重叠比如[1, 3]和[3, 5]不能放同一组。问最少需要分成多少组。例如intervals [[5,10],[6,8],[1,5],[2,3],[1,10]]肉眼可以看出[1,10]这个长区间几乎和所有区间都重叠至少要单独占一组剩下的区间里[2,3]、[6,8]之间没有重叠可以并组但[5,10]和[1,5]端点5重叠也不能同组。最终结果是3组。这个问题本质上是在问同一时刻最多有几个区间“叠在一起”这个最大重叠数就是最少组数。1.3 两道题放在一起看的共同特征两题都涉及“选择顺序”和“全局约束”。2208每次要选一个元素操作2406每次要决定区间放进哪个组如果你凭感觉乱选结果经常不是最优。它们共同指向两个高频工具优先队列堆和排序。2208需要在每次操作时快速拿到当前最大值2406需要在扫描区间时快速找到可复用的组两者都可以用堆把复杂度压到O(n log n)级别。维度2208 数组和减半2406 区间分组数据结构数组、优先队列区间数组、优先队列核心策略每次减半最大元素左端点排序 最小堆维护各组最右端点时间复杂度O(n log n)O(n log n)本质问题最大化单次收益最小化资源组数2. 贪心思路拆解为什么局部最优能推出全局最优2.1 2208为什么每次都减当前最大元素一定最优假设当前数组和是S目标减少量是S / 2。你每次操作能让某个元素变为原来的一半也就是说本次操作带来的“减少量”等于当前元素值 / 2。要想尽快累计到目标减少量直觉上当然是每次让“减少量”尽量大。我一开始想过一个问题比如有两个元素a100和b60目标减少量是80。如果先减100减少50再减50累计75还不够再减25累计100共3次如果先减60减少30再减30累计60再减100减少50累计110也是3次。看起来次数相同那贪心还成立吗关键在于这是特殊场景下碰巧相同换成a100, b99目标减少量55先减100第一次减少50第二次减50变成25累计75达标题先减99第一次减少49.5第二次减49.5累计99也达标还都是两次。再换a100, b1目标减少量是40先减100只需一次就减少50达标题先减1第一次减少0.5再减0.5要减几百次才够。所以贪心的收益不是体现在“局部立刻达标题”而是体现在“把大盘子的价值榨干”——最大元素减半后依然可能比别的小元素大继续减它仍然收益更高。每次取最大值就等价于在保证“每一步都获取最大可得的减少量”而由于每次操作获得的收益是递减的、且相互独立每一步最优的累加就是全局最优。这个证明思路用反证法可以写清楚如果某次操作不选当前最大元素x而选了y那么这次收益y/2一定不大于x/2并且减完y后x仍然原样保留后续收益不会比“先减x再处理y”更好。因此最优解一定包含“每次减最大”这个策略。这里给一个更直观的生活类比你有一堆大小不一的冰块想尽快把它们化成一半。你肯定先拿最大那块去晒因为它融化出的水最多晒完它可能还是很大继续晒它依然划算直到它小到不如第二大的那块才切换目标。这个“切换”的过程恰好就是优先队列每次弹最大值、减半后重新入队的过程。2.2 2406区间分组本质上是在求“最大重叠厚度”把每个区间想象成一段会议时间你要用最少的会议室安排所有会议同一个会议室里不能同时开两场会端点时间也被占用。那么“最少会议室数量”就是所有时刻里“同时进行的会议数量”的最大值。这个结论看起来很直觉但要证明足够严谨一方面任意时刻如果有k个区间重叠这k个区间必然两两不能同组所以至少需要k组因此答案必定大于等于最大重叠数另一方面我们需要证明可以用“最大重叠数”这么多组就安排完不会需要更多。这个构造性证明可以通过“按左端点排序再用最小堆贪心地复用组”来完成。当你把区间按左端点从小到大排序后从左往右扫描。假设当前已经开了若干组每组记录它最后一个区间的右端点也就是“这组最晚的结束时间”。下一个区间[l, r]如果想放进某一组要求这组最后结束时间小于l严格小于因为闭区间端点重合算冲突。在所有结束时间中肯定优先选择“结束时间最早”的那一组来尝试——如果最早的结束时间都大于等于l说明当前所有组都还忙只能新开一组如果最早的结束时间小于l那用这一组放入新区间一定最优因为其他组的结束时间更晚留它们继续占用反而更灵活。这个过程不断维护组的结束时间集合最终组数不会超过最大重叠数因为只有当某个时刻确实同时存在“当前活跃区间数1”的重叠时你才会新开组。两相结合正好证明“最少组数等于最大重叠数”。2.3 贪心的使用前提选了一次不影响后续的“可选择集合”很多新手对贪心最大的困惑是为什么这里能用贪心别的地方不能用答案在于这两道题里每次操作的“选择集合”不会因为你选了某个元素而改变其他元素的相对价值——2208里减半一个数不会影响别的数的大小2406里决定把新区间放入哪一组不会影响后续区间的排序结果。也就是说局部决策不会改变未来的可选范围所以局部最优能叠加成全局最优。反过来像背包问题、旅行商这类问题你选了某件物品就把容量占了会影响后续可选空间贪心就不一定成立。3. 核心实现用堆把贪心落地3.1 2208 的大顶堆写法Python 里heapq是小顶堆想用大顶堆最简单的办法是存入负值。核心流程先算出原数组总和设定目标减少量为总和的一半把所有元素取负后入堆循环里弹出堆顶绝对值最大的元素把它减半再取负入堆同时累计减少量直到减少量大于等于目标值返回操作次数。import heapq from typing import List def halveArray(nums: List[int]) - int: total sum(nums) # 原数组总和 target total / 2 # 需要减少的量 heap [-x for x in nums] # 大顶堆存负数堆顶是绝对值最大的 heapq.heapify(heap) reduced 0.0 ops 0 while reduced target: # 弹出当前最大元素减半后再放回去 cur -heapq.heappop(heap) half cur / 2 reduced half heapq.heappush(heap, -half) ops 1 return ops这段代码有几个细节值得说一下。第一total可能很大但题目给的数值范围在int范围内最后比较时用浮点target注意 Python 浮点精度足够处理到1e-5级别的比较因为每次减半后差值不会出现极小误差导致死循环。第二为什么是cur / 2而不是cur // 2因为题目说的是减半不是整除需要保持浮点精度。第三循环结束条件是reduced target不是sum(heap) target后者的计算成本是 O(n)会拖慢整体性能。3.2 2406 的最小堆写法按左端点排序后用一个最小堆维护“各组的最后右端点”。遍历每个区间时先看堆顶最小的右端点是否小于当前区间的左端点如果严格小于说明有组已经空闲可以复用就把堆顶弹出并用当前区间右端点顶替否则新开一组把右端点直接入堆。最后堆的大小就是最少组数。import heapq from typing import List def minGroups(intervals: List[List[int]]) - int: intervals.sort(keylambda x: x[0]) # 按左端点排序 heap [] # 小顶堆存每个组当前的最后右端点 for left, right in intervals: if heap and heap[0] left: # 最早结束的组已经空闲复用这一组 heapq.heappop(heap) # 无论复用还是新开当前区间的右端点都要入堆 heapq.heappush(heap, right) return len(heap)这里最容易写错的就是heap[0] left和heap[0] left的区别。因为题目定义是闭区间[1,3]和[3,5]端点3重叠不能放同一组所以必须严格小于才能复用。如果题目改成开区间那就对了。这个边界我一开始就踩了坑提交之后发现答案总是比预期大1排查了半天才反应过来。3.3 复杂度分析与数据规模论证2208 的时间复杂度看起来是 O(k log n)其中 k 是操作次数。最坏情况下会操作多少次每次操作至少把一个元素减半最多操作次数不会超过把所有元素都降到非常小的程度但实际题目中目标只是减少总和的一半。可以这样估算每次减少量至少是“当前最小非零元素的一半”而每次取最大值减少量往往远大于这个下界所以操作次数通常远小于 n。不过即使按最坏情况看每次操作都是O(log n)总体也是可以接受的实际提交在n 10^5范围内都能秒过。2406 的复杂度更明确排序 O(n log n)每个区间入堆、出堆各一次总复杂度 O(n log n)空间复杂度 O(n)。这里额外提一个热词相关的点很多人搜“数组排序的几种方法”其实在这类题目里排序不是目的是为了给贪心扫描提供有序的输入。2208 不需要排序因为它要的是随时取最大元素这恰恰是堆的用武之地如果换成一个乱序数组做排序再每次取最大复杂度反而会退化。数据结构选择背后的依据是“你需要什么样的数据访问顺序”而不是“哪个API更酷”。4. 另一种视角差分数组与扫描线4.1 为什么区间重叠可以转成“事件叠加”区间分组的问题还可以用差分数组来做这个思路在热词里也频繁出现比如“数组求区间最大值的算法题”“树状数组模板”“差分数组”等等。核心思想是把每个区间看成两个事件左端点位置“进入量 1”右端点之后的位置“进入量 -1”。如果我们把坐标轴上的每个点扫一遍累加这些事件得到的值就是“当前点的重叠区间数”。那么所有点里重叠数的最大值就是最少组数。这里需要特别小心端点边界。因为闭区间[left, right]中right本身也算区间内所以区间对重叠数的贡献应该是[left, right]闭区间内每个点加1。如果用差分应该在left处 1在right 1处 -1这样扫到right时重叠数还在到right 1才减掉。如果你写成right处 -1就会少算右端点的重叠答案可能偏小。4.2 用事件排序法实现扫描线坐标范围如果很大直接开数组会爆内存所以要先把所有事件排序再从左到右扫。一种简洁写法是from typing import List def minGroups(intervals: List[List[int]]) - int: events [] for left, right in intervals: events.append((left, 1)) # 左端点进入 events.append((right 1, -1)) # 右端点之后离开 events.sort(keylambda x: x[0]) cur 0 max_overlap 0 i 0 while i len(events): pos events[i][0] # 把同一坐标的所有事件一次性处理 while i len(events) and events[i][0] pos: cur events[i][1] i 1 max_overlap max(max_overlap, cur) return max_overlap为什么同一坐标的事件要一次性处理因为如果同一个坐标点上既有离开事件又有进入事件比如[1,3]右端点3的离开事件发生在4另一个区间[4,5]的左端点进入事件发生在4它们并不会在同一时刻叠加。把同一坐标所有事件合并处理可以避免出现中间态的虚高。这个细节在热词“合并重叠区间”“无重叠区间”的很多题解里也是容易忽略的点。4.3 堆方案和差分方案怎么选堆方案的空间复杂度是 O(n)差分事件方案的空间也是 O(n)但差分方案的时间主要是排序事件常数比堆稍大一点。更重要的是思考方式堆方案是“在线”的你边扫区间边维护组状态像开会议室一样一张一张安排差分方案是“离线”的你先算出每个点的重叠度直接取最大值更像是在做统计。实际面试中我建议优先掌握堆写法因为它能直接套用到很多变体题上比如“会议室II”就是一模一样的题目。差分方案则更适合用来验证答案或者当你需要额外知道“哪个点重叠最多”的时候。两种方法都写一遍你对区间问题的理解会明显深一层。5. 实战避坑我在这两题上翻过的车5.1 2208 的浮点精度和循环边界第一版代码我犯了个低级错误把total直接除以2之后存成整数导致目标值比实际小1答案少算一次。第二版我学乖了用浮点target结果又因为比较时用了reduced target导致差一点点就退不出循环。正确的写法是while reduced target并且循环体内部每次减少量都是正数总能收敛。还有一个细节堆里存负数后取出时要记得取反。我见过不少新手在heapq.heappop(heap)之后忘记加负号直接拿负数做除法结果减少量变成负数循环直接死循环。这种错误编译期不会报运行期看起来只是“不结束”特别难排查。建议把取反和减半写成一行cur -heapq.heappop(heap) / 2然后直接reduced cur再把-cur塞回堆这样逻辑最清晰。5.2 2406 的边界条件闭区间和左端点排序最大的坑就是heap[0] left和heap[0] left。因为闭区间端点重叠冲突必须严格小于。题目里如果给你的是开区间比如(1,3)和(3,5)不重叠那就要改成heap[0] left。建议在做题前先看清题目对“重叠”的定义不同平台的表述不完全一致。LeetCode 2406 明确写了闭区间且端点相接触也算重叠所以严格小于是唯一的正解。另一个容易踩的坑是排序时只排左端点够不够。如果两个区间左端点相同优先排右端点小的还是大的其实对于这个题来说左端点相同的情况下它们的入堆顺序不影响最终组数因为堆里维护的是每组右端点左端点相同的区间必然无法放入同一个正在处理位置之前的组里最终堆大小的计算依然正确。不过为了习惯统一我一般会写成intervals.sort(keylambda x: (x[0], x[1]))这能保证在依赖扫描顺序的其他变体题里也不出错。5.3 常见错误速查表题目错误现象原因正确做法2208结果总是比答案小1目标值用整数除法丢了0.5target sum(nums) / 22208程序死循环堆里负数未取反就做除法先取反再减半再取反入堆2208用sum(heap)判断结束每次求和O(n)超时维护累计减少量用reduced判断2406结果偏大用heap[0] left判断复用闭区间必须heap[0] left2406结果偏小差分事件在right处 -1要在right 1处 -12406事件扫描中间态虚高同一坐标事件未合并先合并同一坐标所有事件再更新答案6. 题型延伸这套思路还能直接套到哪些题6.1 “减半”类问题的变体与扩展2208 的变体非常多。比如把目标改成“把数组和减少到小于某个阈值k”那只需要把循环条件换成total - current_sum k即可如果是“每次可以选两个元素同时减半”那堆里每次弹出两个最大值处理如果是“每次操作可以让某个元素减少三分之一”思路完全一样只是减少量的计算方式变了。核心都是用优先队列维护当前最大的操作对象每次都能获取最大收益。这个套路也可以迁移到“合并石子最少代价”一类问题上只是那里用的是小顶堆取两个最小值合并收益模型不同但数据结构的选型逻辑一致。6.2 “区间分组”类题目的全家桶热词里反复出现的“无重叠区间”“合并重叠区间”“会议室II”和2406的关系非常紧密。252 会议室是一道基础判断能不能用一个会议室安排全部会议等价于最大重叠数是否不超过1253 会议室II就是2406的原题435 无重叠区间是求最少移除几个区间能让剩余区间互不重叠思路是排序后贪心保留右端点小的区间56 合并区间则是在排序后看相邻区间的重叠情况做合并。把这些题放在一起刷你会发现排序 堆/双指针几乎覆盖了所有区间类题目的解空间。如果还想挑战更高阶的变体可以试试这类给出很多查询区间和一个值域问每个查询区间包含了多少个点这种题通常会用到扫描线加树状数组本质上也还是“事件 区间贡献”的扩展。热词里提到的“树状数组模板”“二维数组”“指针数组”等都是顺着这个方向延伸出去的。6.3 刷题时的个人复盘建议我自己的习惯是每刷完一组题就停下来问三个问题这题如果数据范围扩大十倍还能不能过这题换成开区间/闭区间答案会怎么变这题能不能用两种不同算法做各自复杂度如何。2208 和 2406 正好适合做这种复盘因为它们实现代码都很短但背后的分析链条很长。尤其是2208你甚至可以手动模拟几轮堆的变化把“为什么每次取最大”在纸上画出来印象会比看十篇题解都深。我个人在实际操作中还有一个体会很多题解喜欢直接贴代码但很少讲“为什么这个贪心是对的”和“为什么边界要这样处理”。如果你刷这两题时能把证明过程也写一遍哪怕只写给自己看之后再遇到“会议室II”“无重叠区间”这类题基本就是送分题了。这也是这篇文章把大量篇幅放在推导和踩坑上的原因——代码你看一眼就会但判断依据和边界意识才是真正值钱的东西。