LeetCode 3296这题我第一眼看到“移山所需的最少秒数”的时候脑子里蹦出来的解法就是优先队列。一座山立在那一排工人每人干一个单位之后越来越慢求最少几秒能全部搞定——这太像并行调度模拟了谁手头最快做完下一块就派给谁。但等我真把这版代码写出来又仔细测了几个边界用例才发现事情没那么简单。优先队列的写法很直觉可它每搬一个单位就要弹一次堆单位高度一旦给到百万千万级这个堆就会成为性能瓶颈。这篇文章我把两条路线都撸一遍优先队列为什么能写、什么情况下会翻车以及更稳的二分答案等差数列判定怎么推、怎么写、怎么避开那几个大家几乎都会踩的坑。1. 题目讲了个啥一座山和一排工人的调度问题1.1 从“移山”这个设定看本质题目本身不复杂。给你一座高度为mountainHeight的山以及一个数组workerTimes第i个工人第一次降低 1 单位高度需要workerTimes[i]秒。关键是后面这句同一个工人干得越多越慢他第k次降低 1 单位高度需要的时间是workerTimes[i] * k。也就是说一个工人的单位耗时序列是w, 2w, 3w, 4w...等差数列递增。这个“越干越慢”的设定本质上是在模拟体力消耗。第一次是满状态后面每一次都要比前一次更吃力。所有工人可以同时开工问的是把整座山完全移平的最少秒数。从建模角度讲它就是一个“多个并行处理器 递增处理时间”的调度问题。难点不在模拟本身而在于你选什么方式去搜索答案。很多人看这个题目第一反应是能不能用优先队列模拟每一秒的决策完全可以但这只是表面上的直观耐不耐得住数据范围的考验就是另一回事了。1.2 这个调度模型天然长着一张“堆”的脸为什么优先队列是第一直觉因为问题里有一个非常典型的贪心结构我们手里有多条“工人生产线”每个人都串行工作谁当前最快能完成下一个单位就让谁去干下一个任务。这种“谁先空出来谁接活”的逻辑就是操作系统里常见的短作业优先调度的变体。你可以在脑子里想象成收银台。几个收银员速度不一样而且干得越久越慢一个新顾客来了正常人都会让预计最早能处理完的那个收银员去接。放在程序里要时刻维护“下一个单位由谁在什么时候完成”最自然的数据结构就是小顶堆堆顶就是当前最早完成下一个单位的工人。在mountainHeight不太大的时候这个解法甚至有点优美。每次弹出一个(时间, 工人编号, 已干次数)记录答案再把该工人下一单位的事件推回堆里。逻辑清晰、边界少、代码短一口气写完也不容易错。问题是这个解法的复杂度是O(mountainHeight * log n)完全跟着山的高度走。一旦数据范围把mountainHeight拉到 1e6、1e7 甚至 1e9堆方案就是肉眼可见的灾难。这也是为什么我后来还是把目光转向了二分答案——先别急把两条路都走一遍再下结论。2. 优先队列解法直观但要看数据规模下菜碟2.1 状态设计把“工人下一次干完的时间”丢进堆优先队列的关键不是堆本身而是状态里要装什么。我用的状态是三元组(finishTime, workerIdx, times)其中finishTime表示这名工人完成“下一个单位”的绝对时刻times表示他这已经是第几次干活了。初始化时所有工人都还没开工所以第i个工人的第一次任务完成时间就是workerTimes[i]。把这些初始事件全部入堆。之后每一轮循环弹出一个finishTime最小的工人这个时刻就是“当前这一个单位被移走的时间”。接下来这名工人要干他的第times 1次活下一次完成时间等于当前完成时间加上workerTimes[i] * (times 1)再把他推回堆里。这里有三个容易写错的地方。第一堆里必须存times不能只存工人编号因为下一次耗时取决于他已经干了几次。第二不能把一个工人未来的所有任务都提前塞进堆那样就破坏了“串行工作”的约束。第三比较元组时如果finishTime相等别指望(t, i, times)一定不报错Python 的元组比较会自动往后比i和times只要都是 int 就没问题但 C 里如果只重载了时间比较就要小心。import heapq def minimum_seconds_heap(mountainHeight: int, workerTimes: list[int]) - int: heap [] for i, w in enumerate(workerTimes): heapq.heappush(heap, (w, i, 1)) # 第一次干活耗时 w ans 0 for _ in range(mountainHeight): t, i, times heapq.heappop(heap) ans t # 这名工人下一次干活的耗时是 workerTimes[i] * (times 1) heapq.heappush(heap, (t workerTimes[i] * (times 1), i, times 1)) return ans这个代码在小数据上非常稳。比如mountainHeight 4, workerTimes [1, 2, 3]跑一下第一次弹出(1, 0, 1)工人 0 在 1 秒完成第一单位第二次弹出(2, 1, 1)工人 1 在 2 秒完成第三次弹出(3, 0, 2)工人 0 在 3 秒完成第二单位第四次弹出(3, 2, 1)工人 2 也在 3 秒完成第一单位。答案 3和我们手算一致。2.2 为什么这种贪心是对的可能有人会问每次都派当前完成最早的人真的能得到全局最优会不会存在一种策略刻意让某个工人休息一下把任务留给后面更合适的人从而总时间更短这个问题的答案是不需要刻意休息。因为所有任务都是等价的“降低 1 单位高度”而且每个工人的耗时序列只和自己的已做次数有关不依赖任务内容。你可以用交换论证去证明假设某个最优调度里在某个时刻出现了“工人 A 明明可以最早完成却让工人 B 先做”的情况那么把这两个任务的顺序交换A 做早了、B 做晚了总完成时间只会更早或不变。反复交换就能得到这种贪心策略给出的调度。所以优先队列模拟的不仅是一个可行方案在这个模型下它确实是最优的。但注意这并不代表堆解法一定适合所有数据范围。算法正确性和工程可行性是两码事这也是我觉得这题特别值得复盘的地方。2.3 复杂度真相堆能不能过全看山有多高优先队列解法的时间复杂度是O(mountainHeight * log n)堆里最多同时有n个工人事件。空间复杂度O(n)。从内存角度看没有任何压力但时间上每移掉一个单位高度就要log n一次重排。如果题目给的mountainHeight在 10^5 以内这个写法基本上能顺利通过代码也足够简洁。但如果哪天你把mountainHeight放大到 10^9哪怕log n再小乘以 1e9 也是天文数字堆每一轮的常数再低也救不回来。所以我的建议是优先队列适合当作理解题意的辅助工具或者拿来对拍小数据验证其它算法真正用来提交时得先看数据范围再决定。这也是我后面为什么一定要写二分答案版的根本原因——解题不能只赌出题人心软。3. 更省事的二分答案把时间当作搜索轴3.1 一秒变成判题器给定 t 秒能不能移完二分答案的核心是把“求最少秒数”这个最优化问题转换成一个判定问题如果给你t秒你能否把整座山移完为什么这样做可行因为“能不能在 t 秒内移完”这件事是单调的。t 越大每个工人能干的活只会越多不会更少。所以一旦某个t可行那么所有比t更大的时间都可