一句话：当某个”门槛”只增不减时，每个元素一辈子只会被”解锁”一次；把已解锁的东西塞进堆里随时取最值，整套流程就从 摊成了 。

直觉：单调的门槛 = 不回头的扫描

很多题目长这样：你手里有一个会变化的量（资金、时间、位置……），每一步只能从”当前够得着”的候选里挑一个最优的去用，用完之后那个量又变了，于是够得着的候选范围只会变大、不会缩小。

这里藏着和双指针一模一样的味道：单调性让你不用回头。

• 双指针靠的是”移动指针让目标单调变化”，所以左右指针各扫一遍就够。
• 这里靠的是”门槛单调上升”，所以每个元素只会越过门槛一次——一旦它被解锁进入候选池，就再也不会退回去。

朴素做法会在每一步都把所有元素重新扫一遍看谁够得着，这就是 的来源。但既然元素只解锁一次，我们完全可以：

1. 用一个按门槛排序的结构（小根堆 / 排好序的数组 + 指针）盯着”下一个即将解锁的元素”；
2. 把已解锁的元素丢进一个按收益排序的大根堆；
3. 每一步直接从大根堆顶拿走收益最大的。

解锁是单向的、总共只发生 次；每次入堆/出堆 。于是总复杂度 。

下面这个动画把 IPO 这道题的”解锁→选取”逐帧拆开了，先看一眼整个流程长什么样：

旗舰例题：LeetCode 502. IPO

给定 个项目，初始资金 。项目 需要资金门槛 才能启动，做完获得纯利润 （利润直接加进资金）。最多做 个，求最终最大资金。

贪心为什么对

每一步的决策是：在当前资金够得着的所有项目里，挑利润最大的那个做掉。

为什么”挑当前能做的里利润最大的”不会亏？关键在于资金 只增不减（利润非负）：

• 现在够得着的项目，将来一定还够得着（门槛没变，钱只多不少）；
• 所以”现在不做、留到以后做”不会让某个项目变得不可达，唯一的代价是占用了一次宝贵的名额；
• 既然名额只有 个，每次就该把名额花在当前可选集合里收益最大的那个上。把利润最大的换成任何别的，最终资金都不会更高。

注意一个常见误解：候选池里没被选中的项目不会消失，它们继续躺在 available 里参与下一轮竞争——我们每轮只是挑走当前的最大值而已。

朴素 O(kN)

最直白的写法：每一轮都遍历所有还没做的项目，找出”够得着且利润最大”的：

class Solution:
    def findMaximizedCapital(self, k, w, profits, capital):
        n = len(profits)
        used = [False] * n
        for _ in range(k):
            best = -1
            for i in range(n):
                if not used[i] and capital[i] <= w and (best < 0 or profits[i] > profits[best]):
                    best = i
            if best < 0:           # 一个都够不着，提前结束
                break
            w += profits[best]
            used[best] = True
        return w

每轮 ，共 轮，最坏 。痛点很明显：每一轮都在重复扫描那些早就够得着的项目。

双堆：让”够得着”只判断一次

既然资金单调上升，一个项目一旦够得着就永远够得着。那就别每轮重扫了：

• locked：小根堆，按 capital 排序。堆顶永远是”门槛最低、最快被解锁”的项目。
• available：大根堆，按 profit 排序。装的是已解锁、还没做的项目。

每一轮：先把所有 capital ≤ w 的项目从 locked 搬进 available（这一步是单向的，搬过去就不回来），再从 available 弹出利润最大的做掉。

import heapq

class Solution:
    def findMaximizedCapital(self, k, w, profits, capital):
        locked = list(zip(capital, profits))   # 小根堆，按 capital
        heapq.heapify(locked)
        available = []                          # 大根堆，存 -profit
        for _ in range(k):
            # ① 解锁：把所有够得着的搬进 available
            while locked and locked[0][0] <= w:
                _, pro = heapq.heappop(locked)
                heapq.heappush(available, -pro)
            # ② 没得选了，提前结束
            if not available:
                break
            # ③ 做掉利润最大的
            w -= heapq.heappop(available)       # 减负数 = 加利润
        return w

为什么内层 while 不会把复杂度拉回 O(N²)

第一眼看上去，外层 轮里嵌了个 while，像是 。但请盯住 locked 堆的大小：

每个项目最多被 heappop(locked) 弹出一次——弹出后它就进了 available，再也不会回到 locked。所以整个算法里，内层 while 的 pop 操作累计最多执行 次，而不是每轮 次。这就是摊还分析（amortized analysis）：单看某一轮 while 可能跑很多次，但跨越所有轮次求和，总量被 卡死。

• 解锁（locked 出堆 + available 入堆）：总计 。
• 选取（available 出堆）：最多 次，。

合起来 。

替代写法：排序 + 指针

locked 那个小根堆其实可以换成”排好序的数组 + 一个只前进的指针”——因为我们只关心”门槛最低的下一个”，而门槛是单调访问的：

import heapq

class Solution:
    def findMaximizedCapital(self, k, w, profits, capital):
        projects = sorted(zip(capital, profits))   # 按 capital 升序
        available = []
        i, n = 0, len(projects)
        for _ in range(k):
            while i < n and projects[i][0] <= w:
                heapq.heappush(available, -projects[i][1])
                i += 1
            if not available:
                break
            w -= heapq.heappop(available)
        return w

指针 i 只增不减，正是”单调阈值”的直接体现。两种写法复杂度相同，排序版常数更小，也更能暴露”门槛单调”这个本质。

套路抽象

把这个模式抽出来，识别信号和组件如下：

识别信号：题目里有一个单调变化的阈值（资金、时间、坐标），每步从”当前阈值够得着的候选”里取一个最优的，取完阈值又单调变化。

角色	在 IPO 里	在通用模板里
单调阈值	资金 （只增）	时间 / 位置 / 预算
解锁结构	locked 小根堆（按 capital）	排序数组 + 指针，或按”激活条件”排序的堆
候选池	available 大根堆（按 profit）	按”取舍指标”排序的堆
每步动作	解锁全部够得着的 → 取利润最大	解锁全部满足条件的 → 取最优

同族题：

• 1851. 包含每个查询的最小区间：把查询按值排序（单调阈值），区间按左端点排序丢进候选；候选堆按区间长度取最小。
• 会议室 II / 1834. 单线程 CPU：任务按到达时间解锁（单调时间），候选堆按处理时长/优先级取最优。
• Dijkstra 最短路：距离 单调不减，每次从堆里取当前最近的点松弛——本质也是”单调阈值 + 堆”。

核心机制：解锁是单向的

整个套路的复杂度红利，全压在一句话上：因为阈值单调，每个元素一辈子只会被”解锁”一次。

• 解锁指针（IPO 的 locked 堆、1851 的指针 i）只前进、不回退；
• 一旦元素进了候选池，就再也不回到”锁住”的状态；
• 配套的”懒删除”只看候选池的堆顶：堆顶若已经失效（如 1851 里右端点 < q）就弹掉，弹掉的元素永久丢弃，绝不捡回。

正因如此，”解锁 + 弹出”这些动作累计最多 次（而不是每轮 ），乘上单次堆操作 ，才有总复杂度 。这套摊还的地基，就是阈值单调。

一个容易踩的澄清：外层循环不必是那个单调量

很自然会以为”外层循环就该遍历单调阈值”。其实不一定——必须单调的是阈值，外层循环只是推进阈值的引擎。两者经常重合，但不是一回事：

	1851	IPO
外层循环在数什么	排好序的 queries	k 次挑选（for _ in range(k)）
真正的单调阈值	query 值 q	资金 w
阈值 = 外层循环吗	是	不是——w 是挑选的副作用在涨

IPO 的外层是”做 k 个项目”，跟单调量 w 根本不是同一个东西；w 因为利润非负而天生只增，于是解锁指针自动只前进。而 1851 的阈值就是 query 本身、不天生有序，所以你必须主动 sort(queries) 再按序遍历——这才让外层循环”被迫”等于那个单调量。

为什么 1851 非排序不可？因为”剔除即永久丢弃 + 只看堆顶”的懒删除，正确性完全押在阈值单调上：你为某个 q 把 r < q 的区间弹掉，断言”以后用不上”，这只在后续所有 q' 都 时成立。一旦乱序处理，被大 q 丢掉的区间对更小的 q' 可能又合法了，懒删除立刻出错。

所以判断一道题能不能套这个模板，标准很简单：

问自己——解锁指针会回退吗？已丢弃的元素会需要捡回来吗?
只要两个答案都是”不会”，单调性就立住了，外层循环长什么样都无所谓。

再练一道：LeetCode 1834 单线程 CPU

给一组任务 tasks[i] = [enqueueTime, processingTime]。CPU 单核，空闲时如果有可执行任务，就挑处理时间最短的（同长挑原下标最小的）；执行期间不被打断。返回任务的执行顺序。

这题正好把前面那条澄清坐实了——单调阈值是”当前时刻 time“，但外层循环不是它：外层是”直到所有任务都输出完”，time 要么因执行任务而增、要么在 CPU 空闲时跳变到下一个任务的到达时刻，全程只增不减。解锁指针也只前进。

• 单调阈值：time（时钟，只增）
• 解锁结构：任务按 enqueueTime 排序 + 一个只前进的指针
• 候选池：大根……不，小根堆，按 (processingTime, 原下标) 取最小
• 每步动作：解锁所有 enqueueTime ≤ time 的任务 → 取时长最短的执行

import heapq

class Solution:
    def getOrder(self, tasks):
        tasks = sorted((enq, dur, i) for i, (enq, dur) in enumerate(tasks))
        heap = []                 # (处理时长, 原下标)
        ans = []
        time = 0
        i, n = 0, len(tasks)
        while len(ans) < n:
            # ① 解锁：所有已到达的任务进候选堆
            while i < n and tasks[i][0] <= time:
                _, dur, idx = tasks[i]
                heapq.heappush(heap, (dur, idx))
                i += 1
            # ② CPU 空闲：把时钟跳到下一个任务的到达时刻
            if not heap:
                time = tasks[i][0]
                continue
            # ③ 取时长最短（同长取原下标小）的执行
            dur, idx = heapq.heappop(heap)
            time += dur
            ans.append(idx)
        return ans

三个写法上的关键点，全是这个套路的直接体现：

1. 原下标随元组一起排序（(enq, dur, i)），解锁、出堆全程不丢，省掉一套额外的索引映射。
2. 空闲时只把 time 跳到 tasks[i][0] 然后 continue——回到循环顶部，唯一的解锁 while 自然把新到达的任务收进来，不必把解锁逻辑复制第二遍。
3. 元组 (dur, idx) 天然实现 tie-break：”时长优先、同长比原下标”由元组比较自动完成。

复杂度同样是 ：每个任务入堆一次、出堆一次，指针 i 单调前进。

记忆法

和双指针那句口诀同源：

抓住单调性，就不用回头。

双指针是指针不回头，这里是门槛不回头——门槛单调上升 ⇒ 元素只解锁一次 ⇒ 把”够得着的”丢进堆里随时取最值。看到”边界单调 + 每步取最值”，先往这个模板上套。

思考题

点开看三道思考题

① 为什么内层 while 不会让总复杂度退化成 ？

因为 locked 里每个项目一生只会被 pop 一次（pop 出来就进了 available，不再回来）。跨越所有 轮，while 内的操作累计最多 次，而非每轮 次。这就是摊还：单轮可能爆发，总量被 封顶。

② 如果利润可以是负数，这个贪心还对吗？

不对。负利润会让资金 不再单调上升，”现在够得着将来一定够得着”的前提崩了——做了一个负利润项目，可能反而让后面某些项目变得做不起。”单调阈值”是整个套路的地基，地基塌了套路就不成立。

③ 为什么要两个堆，不能只用一个？

因为两个堆的排序键不同：locked 按 capital（决定”何时解锁”），available 按 profit（决定”先做谁”）。一个堆没法同时按两个维度给你最值。本质上 locked 回答”下一个解锁谁”，available 回答”下一步做谁”，职责分离。

LeetCode 链接

• 502. IPO
• 1851. 包含每个查询的最小区间
• 1834. 单线程 CPU
• 253. 会议室 II