UNIT 01精确值与边界
#704 二分查找
- 候选或优先级
- 有序数组中可能包含目标的下标区间。
- 收缩或淘汰
- 比较中点与目标，保留仍可能命中的一半。
- 结构不变量
- 若目标存在，其位置仍在候选区间内。
- 边界检查
- 空区间终止；闭区间和半开区间的更新规则不能混用。
迁移 · #374 猜数字大小猜数字把数组比较换成具有单调反馈的接口判断。
先说清契约，再独立实现进入本单元 ↗
第6章｜二分、堆与优先队列
Unit 00 · 前置知识、定义、边界契约与工作原理
仅本次页面有效
00
Candidate CompressionBinary Search · Heap · Priority Queue
二分负责证明一大片候选不可能，
堆负责始终暴露下一位优先候选。
这两类结构都在避免维护“全部答案细节”：二分依靠单调性压缩静态候选空间；堆依靠局部堆序维护动态候选边界。先理解它们保存什么信息、舍弃什么信息，再学习代码模板。
发现上次学习记录可恢复阶段、动画、代码、场景判断和滚动位置。
必要前置定义这些术语会贯穿 Unit 01–10
候选空间 Candidate Space
当前仍可能成为答案的位置、数值或对象。算法通过排除、保留或重组候选空间推进。
单调判定 Predicate
布尔结果沿候选顺序最多发生一次切换，如 False…False, True…True。这是二分答案的核心前提。
边界 Boundary
状态切换位置。常见目标包括第一个满足条件的位置、最后一个不超过目标的位置和插入点。
区间契约 Interval Contract
明确 left/right 是否属于候选、循环何时结束、每次更新排除了哪些位置。
可行性函数 Feasible
把“答案是否足够大、速度是否够快”等复杂问题压缩为 True/False，供答案空间二分使用。
不变量 Invariant
每轮前后始终成立的陈述，例如“答案仍在区间内”或“堆中保留当前最大的 K 个元素”。
完全二叉树
除最后一层外全部填满，最后一层从左到右连续，因此可用数组无空洞表示。
堆序 Heap Order
只约束父子局部关系。最小堆保证父节点不大于孩子，但不保证数组整体有序。
优先队列 Priority Queue
抽象接口：插入、查看和弹出最高优先级项。堆是常用实现，但二者不是同一概念。
候选前沿 Frontier
多路合并或图搜索中，只维护下一步可能被选中的少量对象，而不是一次展开全部数据。
Top-K 保留不变量
大小为 K 的最小堆可保存当前最大的 K 项，堆顶是这 K 项中的最小边界。
稳定比较 Tie-breaker
优先级相同且对象不可比较时，使用整数序号组成 (priority, tie, item)。
CHAPTER 06 / THE COGNITIVE ATLAS
第 6 章 · 认知梯度全景图
二分、堆与优先队列：缩小搜索空间，用堆维护顺序与动态候选集合。
贯穿本章的统一框架二分维护仍可能包含答案的区间；堆维护当前候选的淘汰或输出边界。两者都先明确边界含义。
从基础到复合任务，每一步增加一种决策
这里的梯度描述认知任务的递进，不等同于题库的难度标签。点击题目可进入对应单元。
起点 · Unit 00 二分、堆与优先队列基础。先理解状态、操作与不变量，再沿下列路线练习。
- 01
- 02
- 03
- 04
- 05
每道题在框架中的具体形式
用同一组问题定位每个单元，再观察迁移题改变了哪个条件。进入写代码环节后，学习地图会收起，留出独立思考的空间。
UNIT 02精确值与边界
#35 搜索插入位置
- 候选或优先级
- 第一个不小于目标的位置，答案允许落在数组末尾之后。
- 收缩或淘汰
- 根据中点是否满足条件，持续收缩到边界。
- 结构不变量
- 左侧已经证明太小，右侧已经证明不小于目标。
- 边界检查
- 目标比所有元素大时插入位置等于数组长度。
迁移 · #34 在排序数组中查找元素的第一个和最后一个位置首末位置分别找第一个不小于与第一个大于目标的边界。
先说清契约，再独立实现进入本单元 ↗
UNIT 03结构与答案空间
#153 寻找旋转排序数组中的最小值
- 候选或优先级
- 旋转有序数组中最小值的候选下标。
- 收缩或淘汰
- 用中点与右边界的关系判断最小值所在区域。
- 结构不变量
- 最小值一直保留在当前闭区间。
- 边界检查
- 无旋转、单元素；无重复是辨别方向的重要条件。
迁移 · #154 寻找旋转排序数组中的最小值 II允许重复时，相等信息不能判定方向，安全缩边可能退化为线性。
先说清契约，再独立实现进入本单元 ↗
UNIT 04结构与答案空间
#33 搜索旋转排序数组
- 候选或优先级
- 旋转数组中仍可能包含目标的范围。
- 收缩或淘汰
- 先判断哪一半有序，再用该半的数值范围决定保留区域。
- 结构不变量
- 目标若存在就没有被收缩步骤删除。
- 边界检查
- 目标缺失与位于分界处；不能认为整个范围始终有序。
迁移 · #81 搜索旋转排序数组 II重复值可能掩盖有序半区，需要先处理信息不足的边界。
先说清契约，再独立实现进入本单元 ↗
UNIT 05结构与答案空间
#875 爱吃香蕉的珂珂
- 候选或优先级
- 吃香蕉的整数速度与总耗时可行性。
- 收缩或淘汰
- 速度越大耗时越小，二分寻找第一个满足时限的速度。
- 结构不变量
- 最小可行速度始终处于当前答案区间。
- 边界检查
- 每堆耗时向上取整；可行性必须针对整批香蕉。
迁移 · #1011 在 D 天内送达包裹的能力运输能力用顺序装载模拟所需天数，仍寻找第一个可行容量。
先说清契约，再独立实现进入本单元 ↗
UNIT 06第 K 名与分区
#703 数据流中的第 K 大元素
- 候选或优先级
- 数据流中最大的至多 k 个值组成的最小堆。
- 收缩或淘汰
- 新值到达时补入或替换最弱候选，控制堆容量。
- 结构不变量
- 数量足够时堆顶就是已见全部数据的第 k 大值。
- 边界检查
- 构造阶段可能不足 k 个值，不能把堆顶称为已有的第 k 名。
迁移 · #215 数组中的第 K 个最大元素离线数组只需一次扫描，也可进一步比较快速选择。
先说清契约，再独立实现进入本单元 ↗
UNIT 07第 K 名与分区
#215 数组中的第 K 个最大元素
- 候选或优先级
- 离线数组中目标升序下标 n−k 与当前分区区间。
- 收缩或淘汰
- 依据基准分区后的排名，保留目标下标所在区。
- 结构不变量
- 目标排名始终保留；分区两侧满足所用分区规则。
- 边界检查
- 重复值和基准选择影响分区；平均与最坏复杂度不同。
迁移 · #347 前 K 个高频元素高频元素先统计频次，把候选优先级从数值改为频次。
先说清契约，再独立实现进入本单元 ↗
UNIT 08优先级的语义
#347 前 K 个高频元素
- 候选或优先级
- 不同元素的频次候选，以及保留前 k 名的堆或频次桶。
- 收缩或淘汰
- 按频次淘汰最弱候选，或从高频桶向低频桶收集。
- 结构不变量
- 已保留或已收集候选的频次满足前 k 名目标。
- 边界检查
- 频次和原值不能混淆，桶下标表示出现次数。
迁移 · #973 最接近原点的 K 个点最近点把频次最大改为距离最小，淘汰边界的方向反转。
先说清契约，再独立实现进入本单元 ↗
UNIT 09优先级的语义
#973 最接近原点的 K 个点
- 候选或优先级
- 至多 k 个点，优先级为平方距离，边界是最远保留点。
- 收缩或淘汰
- 更近的新点替换当前最远候选。
- 结构不变量
- 保留集合始终是已处理点中距离最小的 k 个候选。
- 边界检查
- 平方距离可避免开方；最小目标通常需要最大淘汰边界。
迁移 · #23 合并 K 个升序链表K 路合并不再保留 Top-K，而是每一路只保存当前最小前沿。
先说清契约，再独立实现进入本单元 ↗
UNIT 10动态前沿与平衡
#23 合并 K 个升序链表
- 候选或优先级
- 每条非空有序链贡献一个未输出前沿，放入最小堆。
- 收缩或淘汰
- 弹出全局最小前沿，输出后补入同一来源的后继。
- 结构不变量
- 堆中每一路最多一个前沿，堆顶是所有未输出值的最小者。
- 边界检查
- 空链、相同值与对象比较，来源需能区分。
迁移 · #378 有序矩阵中第 K 小的元素有序矩阵把每行视为来源，后继由链表引用改为列索引。
先说清契约，再独立实现进入本单元 ↗
UNIT 11动态前沿与平衡
#295 数据流的中位数
- 候选或优先级
- 较小一半的最大堆与较大一半的最小堆。
- 收缩或淘汰
- 插入后保持跨堆有序，并把数量调整到相等或下半多一个。
- 结构不变量
- 下半最大值不大于上半最小值，两堆大小差受控。
- 边界检查
- 奇偶数量分别读取一个或两个边界值。
迁移 · #480 滑动窗口中位数滑窗中位数增加过期删除、延迟清理和有效数量平衡。
先说清契约，再独立实现进入本单元 ↗
两种候选压缩机制先理解信息结构，再操作算法
当前核心定义
单调判定的结果沿候选顺序最多切换一次。
当前不变量
尚未开始具体算法；先识别候选空间能够被哪种证据压缩。
当前决策依据
二分看“能否排除连续区间”，堆看“是否只需持续获得局部最高优先级”。
候选数量—
比较或查询次数0
当前边界/堆顶—
结构高度—
当前结论—
模板 A｜寻找第一个满足条件的位置
def first_true(left, right, feasible):
while :
mid =
if feasible(mid):
else:
return left
模板 B｜用大小 K 的最小堆维护第 K 大
import heapq
def kth_largest(nums, k):
heap = []
for value in nums:
if len(heap) > k:
return
策略分类全部正确后完成两个最小模板。提示与骨架不会计为掌握。
提示 1 / 5先分别写清两个不变量：二分保留第一个 True；大小为 K 的堆保留当前最大 K 项。
第6章 Unit 00 Skill卡
二分与堆都通过少维护信息提高效率：二分只维护仍可能包含答案的区间；堆只维护父子局部顺序和堆顶边界。选择结构前，先判断问题需要的是单调空间排除，还是动态优先候选。
二分触发信号候选有顺序，判断结果单调，目标是元素或状态边界
二分核心不变量答案始终保留在当前候选区间中
堆触发信号动态插入、反复取极值、Top-K或多路前沿
堆核心不变量完全二叉树结构＋父子局部堆序
关键区分优先队列是接口；堆是常用实现；堆数组不是排序数组
推荐下一题LeetCode #704 二分查找
进入正式题目前的能力检查
完成不是“看过定义”，而是能把问题语言翻译成候选空间、状态判定和维护不变量。
二分前提能写出候选顺序与单调判定
区间契约能解释每次更新排除了谁
边界语义能区分精确命中与 first_true
堆结构能由索引定位父子并解释局部堆序
动态候选能说明 Top-K 或多路前沿为何只需堆
Python 契约能正确使用 heapq 与元组 tie-breaker
下一单元：LeetCode #704 二分查找
本页完成后不会自动跳转。先停留检查自己的区间契约，再手动进入第一个正式二分页面。