02.3.2.4 优先队列、堆与栈队列综合
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.2 栈与队列、单调栈
02.3.2.4-001 堆是什么结构?
一句话结论
堆是满足堆序的完全二叉树:大顶堆父节点 ≥ 子节点,小顶堆父节点 ≤ 子节点;堆顶为最值;通常用数组存储,支持插入与取最值 O(log n)。
概念解释
- 堆序:父子大小关系。
- 完全二叉树:层内填满。
- 最值:堆顶。
原理流程
- 数组表示二叉树。
- 插入后上浮维护堆序。
- 取堆顶后下沉维护。
代码 / 图示
大顶堆:
10
/ \
8 9
/ \ /
3 5 7
常见误区
- 误区:堆是有序数组;正解:只保证父子关系,兄弟无序。
- 误区:大顶堆根最小;正解:大顶堆根最大。
追问
- Q:堆用于什么? A:优先队列、Top-K、中位数、调度。
- Q:堆是平衡树吗? A:不是,不保证左右子树大小有序。
02.3.2.4-002 堆的数组表示怎么映射下标?
一句话结论
下标从 0 起:父节点 (i-1)/2,左孩子 2i+1,右孩子 2i+2;完全二叉树紧凑存数组,无空指针;边界下标越界需判断。
概念解释
- 层序编号。
- 父子公式。
- 数组连续存储。
原理流程
- 根下标 0。
- 按层序填数组。
- 公式定位父子。
代码 / 图示
i 父:(i-1)/2
左:2i+1
右:2i+2
常见误区
- 误区:下标从 1 起公式混用;正解:0 起与 1 起公式不同,统一口径。
- 误区:孩子下标越界不判;正解:下沉前检查孩子存在。
追问
- Q:1 起下标公式? A:父 i/2,左 2i,右 2i+1。
- Q:叶子节点判断? A:左孩子下标 ≥ 长度。
02.3.2.4-003 堆插入与上浮怎么做?
一句话结论
新元素放数组末尾,与父节点比较,违反堆序则交换并继续上浮到根;O(log n) 比较与交换;大顶堆上浮到父更大为止。
概念解释
- 末尾插入。
- 上浮:与父交换。
- 堆序恢复。
原理流程
- 追加末尾。
- 与父比较。
- 违反则交换,指针上移。
代码 / 示例
void push(int x) {
heap[size++] = x;
int i = size - 1;
while (i > 0) {
int p = (i - 1) / 2;
if (heap[p] >= heap[i]) break; // 大顶堆
swap(p, i); i = p;
}
}
常见误区
- 误区:插入后全局排序;正解:只上浮到满足父子关系。
- 误区:上浮到根才停;正解:父已满足堆序即停。
追问
- Q:上浮交换次数? A:树高 O(log n)。
- Q:相等元素交换吗? A:相等不违反堆序,可停。
02.3.2.4-004 删除堆顶与下沉怎么做?
一句话结论
末尾元素覆盖堆顶,size 减一;从堆顶向下与较大/较小孩子比较,违反堆序则交换并下沉;O(log n);大顶堆选较大孩子交换。
概念解释
- 堆顶移除。
- 末尾补位。
- 下沉恢复堆序。
原理流程
- 堆顶 = 末尾元素。
- size 减一。
- 选合适孩子比较交换,继续下沉。
代码 / 示例
int pop() {
int top = heap[0];
heap[0] = heap[--size];
int i = 0;
while (true) {
int l = 2 * i + 1, r = l + 1, best = i;
if (l < size && heap[l] > heap[best]) best = l;
if (r < size && heap[r] > heap[best]) best = r;
if (best == i) break;
swap(i, best); i = best;
}
return top;
}
常见误区
- 误区:下沉选孩子不比较大小;正解:大顶堆选较大孩子,小顶堆选较小。
- 误区:末尾元素直接丢弃;正解:补到堆顶再下沉。
追问
- Q:堆空 pop? A:先判空。
- Q:下沉到叶子? A:无孩子可交换即停。
02.3.2.4-005 建堆复杂度为什么是 O(n)?
一句话结论
自底向上逐个下沉建堆,叶子无需下沉;总下沉步数按层求和收敛为 O(n),不是 O(n log n);整体线性。
概念解释
- 自底向上。
- 层代价:低层节点多但浅。
- 级数求和收敛。
原理流程
- 从最后一个非叶子节点向前。
- 逐个下沉。
- 求和各层下沉步数。
代码 / 图示
第 h 层节点数 2^k,下沉距离 h-k
Σ 2^k(h-k) = O(n)
常见误区
- 误区:逐个插入建堆 O(n);正解:逐个插入是 O(n log n),自底向上建堆才 O(n)。
- 误区:堆排序建堆 O(n log n);正解:建堆 O(n),排序交换 O(n log n)。
追问
- Q:面试怎么证明? A:按层节点数乘下沉距离求和。
- Q:两种建堆区别? A:插入法简单但慢,原地建堆快。
02.3.2.4-006 Top-K 问题用堆怎么做?
一句话结论
求前 K 大维护大小 K 的小顶堆:新元素比堆顶大则替换堆顶;求前 K 小用大顶堆;O(n log K) 时间 O(K) 空间,适合流式数据。
概念解释
- 堆规模 K。
- 堆顶为当前边界。
- 超界替换。
原理流程
- 先放 K 个入堆。
- 后续元素与堆顶比较。
- 更优则替换下沉。
代码 / 示例
// 前 K 大:小顶堆
Queue<Integer> heap = new PriorityQueue<>();
for (int x : nums) {
if (heap.size() < k) heap.offer(x);
else if (x > heap.peek()) { heap.poll(); heap.offer(x); }
}
常见误区
- 误区:前 K 大用大顶堆;正解:小顶堆淘汰最小,保留 K 大。
- 误区:堆规模 n;正解:固定 K。
追问
- Q:K 接近 n? A:log K 接近 log n,可直接排序。
- Q:流式数据? A:堆无需存全量,O(K) 空间。
02.3.2.4-007 数组中第 K 大元素(LC 215)怎么做?
一句话结论
小顶堆维护 K 个最大元素,堆顶即第 K 大;O(n log K) 时间 O(K) 空间;快速选择平均 O(n) 为对照方案。
概念解释
- 第 K 大:K 个最大中的最小。
- 小顶堆堆顶。
- 流式与离线均可。
原理流程
- 堆维护 K 大。
- 新元素超堆顶则替换。
- 堆顶为答案。
代码 / 示例
public int findKthLargest(int[] nums, int k) {
Queue<Integer> heap = new PriorityQueue<>();
for (int x : nums) {
heap.offer(x);
if (heap.size() > k) heap.poll();
}
return heap.peek();
}
常见误区
- 误区:第 K 大用大顶堆取 K 次;正解:大顶堆也可,但 O(n log n),小顶堆 O(n log K)。
- 误区:K 越界;正解:按题目保证 1≤K≤n。
追问
- Q:快速选择最坏复杂度? A:随机划分平均 O(n),最坏 O(n²)。
- Q:堆法稳定性? A:不要求顺序,重复值按堆实现。
02.3.2.4-008 数据流中位数(LC 295)双堆怎么做?
一句话结论
大顶堆放较小一半(堆顶为左半最大),小顶堆放较大一半(堆顶为右半最小);插入后调整两堆大小差不超过 1;中位数取堆顶或两堆顶平均;O(log n) 插入 O(1) 取中位数。
概念解释
- 左半:大顶堆。
- 右半:小顶堆。
- 平衡:大小差 ≤1。
原理流程
- 新元素先入左大顶堆。
- 左堆顶移右堆,保证右半 ≥ 左半。
- 不平衡则回迁。
代码 / 示例
class MedianFinder {
private final Queue<Integer> left = new PriorityQueue<>((a, b) -> b - a);
private final Queue<Integer> right = new PriorityQueue<>();
public void addNum(int num) {
left.offer(num);
right.offer(left.poll());
if (right.size() > left.size()) left.offer(right.poll());
}
public double findMedian() {
if (left.size() > right.size()) return left.peek();
return (left.peek() + right.peek()) / 2.0;
}
}
常见误区
- 误区:两堆方向搞反;正解:左大顶、右小顶。
- 误区:插入后不调整平衡;正解:大小差超过 1 需回迁。
追问
- Q:奇数个中位数? A:较多一侧堆顶。
- Q:偶数个? A:两堆顶平均。
02.3.2.4-009 滑动窗口最大值(LC 239)单调队列怎么做?
一句话结论
双端队列存下标,队首为窗口最大值下标;入队时队尾弹出比当前小的元素维护递减;队首下标越出窗口则弹出;O(n) 时间 O(k) 空间。
概念解释
- 递减队列:队首最大。
- 队尾淘汰小值。
- 队首淘汰过期。
原理流程
- 新元素入队前弹队尾更小。
- 队首过期弹出。
- 窗口形成后队首为答案。
代码 / 示例
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> dq = new ArrayDeque<>();
int[] ans = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
dq.offerLast(i);
if (i >= k - 1) ans[i - k + 1] = nums[dq.peekFirst()];
}
return ans;
}
常见误区
- 误区:用大顶堆求窗口最大;正解:堆需淘汰过期元素 O(n log n),单调队列 O(n)。
- 误区:相等元素弹出;正解:按口径,相等可保留以延后过期。
追问
- Q:队列存什么? A:下标,判断过期与取值。
- Q:窗口最小值? A:队列方向反转,递增维护。
02.3.2.4-010 单调队列模板有哪些固定步骤?
一句话结论
① 队首淘汰过期下标;② 队尾维护单调方向弹出破坏顺序元素;③ 当前下标入队;④ 窗口形成后取队首;四步对最大/最小通用,只改比较方向。
概念解释
- 过期:下标 < 窗口左界。
- 单调:队首最值。
- 入队:队尾挂接。
原理流程
- 清过期队首。
- 清队尾破坏单调者。
- 入队。
- 记录队首。
代码 / 图示
for i:
队首过期 → 出队首
队尾劣于当前 → 出队尾
入队尾
窗口满 → 答案队首
常见误区
- 误区:先入队再清过期;正解:先清过期再维护队尾。
- 误区:队尾弹出条件写反;正解:最大用
<=弹小,最小用>=弹大。
追问
- Q:单调队列与单调栈区别? A:队列两端操作,栈只一端。
- Q:每个元素入队出队几次? A:各一次,O(n)。
02.3.2.4-011 最小栈(LC 155)怎么设计?
一句话结论
主栈存全部元素,辅助栈同步存当前最小值;push 时辅助栈压入与栈顶较小值;pop 两栈同步弹出;getMin 取辅助栈顶;O(1) 各操作,空间 O(n)。
概念解释
- 主栈:元素。
- 辅助栈:对应最小值。
- 同步压弹。
原理流程
- push:主栈压值,辅助栈压
min(值, 辅助栈顶)。 - pop:两栈同弹。
- getMin:辅助栈顶。
代码 / 示例
class MinStack {
private final Deque<Integer> st = new ArrayDeque<>();
private final Deque<Integer> min = new ArrayDeque<>();
public void push(int val) {
st.push(val);
min.push(min.isEmpty() ? val : Math.min(val, min.peek()));
}
public void pop() { st.pop(); min.pop(); }
public int top() { return st.peek(); }
public int getMin() { return min.peek(); }
}
常见误区
- 误区:辅助栈只压更小值;正解:同步压当前最小值,弹栈后才能恢复上一个最小。
- 误区:pop 只弹主栈;正解:两栈同步。
追问
- Q:重复最小值? A:辅助栈同步重复压,弹出后仍有副本。
- Q:能否 O(1) 额外空间? A:存差值方案可减少辅助,实现更复杂。
02.3.2.4-012 最小栈辅助栈为什么要同步压最小值?
一句话结论
若只压新的更小值,弹出当前最小值后,辅助栈顶丢失之前的次小值;同步压入“到当前为止的最小值”,每弹一层都有对应最小;栈与辅助栈一一对应。
概念解释
- 一一对应:每层一个最小值。
- 弹栈恢复。
- 重复值保留。
原理流程
- 每层记录当前最小。
- 弹出后回到上一层最小。
- 辅助栈长度等于主栈。
代码 / 图示
主栈: 5 3 7 2
辅助: 5 3 3 2
常见误区
- 误区:辅助栈只存递减最小值;正解:非更小元素也要压当前最小。
- 误区:弹主栈后辅助栈滞后;正解:同步弹出。
追问
- Q:差值法怎么省空间? A:栈存与最小值的差,更新最小值,细节按实现。
- Q:最大栈同理吗? A:方向反转即可。
02.3.2.4-013 栈与队列综合设计题怎么拆解?
一句话结论
先明确接口语义(栈 LIFO / 队列 FIFO / 最值),再选基础结构(数组/链表/双栈/双堆),最后核对每个操作的复杂度与边界;常见组合:两栈队列、两队列栈、最小栈、双堆中位数。
概念解释
- 语义:操作顺序。
- 结构:底层载体。
- 复杂度:操作代价。
原理流程
- 列接口与顺序要求。
- 选模拟结构。
- 验证边界与复杂度。
代码 / 图示
顺序要求 → 栈/队列
最值要求 → 辅助栈/堆
常见误区
- 误区:上来就写代码不明确语义;正解:先定出队/出栈规则。
- 误区:忽略淘汰与同步;正解:双结构状态一致。
追问
- Q:设计题要考虑扩容吗? A:按题目容量要求,固定或动态说明。
- Q:线程安全? A:题目未要求时按单线程实现。
02.3.2.4-014 堆与红黑树、排序怎么对比?
一句话结论
堆 O(log n) 插入、取堆顶 O(log n),但不支持有序遍历与任意查找;红黑树 O(log n) 增删查且有序;全量排序 O(n log n);Top-K 与最值场景堆更轻量。
概念解释
- 堆:只维护最值。
- 平衡树:全序维护。
- 排序:一次性全量有序。
原理流程
- 看是否需要有序遍历。
- 看是否只需最值。
- 选结构。
代码 / 图示
Top-K / 最值:堆
有序范围查询:平衡树
一次性排序:排序算法
常见误区
- 误区:堆支持按序输出全部;正解:反复取堆顶才逐步有序。
- 误区:堆查找任意元素 O(log n);正解:堆不支持高效查找。
追问
- Q:堆排序? A:反复取堆顶 O(n log n),原地但不稳定。
- Q:优先队列底层? A:二叉堆常见。
02.3.2.4-015 堆排序思路是什么?
一句话结论
先建大顶堆,反复取堆顶与末尾交换,堆规模减一再下沉;升序用大顶堆;O(n log n) 时间 O(1) 额外空间,不稳定。
概念解释
- 建堆 O(n)。
- 取顶交换。
- 下沉恢复。
原理流程
- 原地建大顶堆。
- 堆顶换末尾。
- 规模减一,下沉堆顶。
代码 / 图示
大顶堆 → 最大值在根
交换到末尾 → 剩余堆下沉
常见误区
- 误区:堆排序稳定;正解:交换跨距大,不稳定。
- 误区:建堆 O(n log n);正解:建堆 O(n),排序阶段 O(n log n)。
追问
- Q:为什么实际少用堆排序? A:缓存局部性不如快排,不稳定。
- Q:小顶堆排升序? A:小顶堆取最小放末尾方向相反,按实现口径。
02.3.2.4-016 优先队列比较器怎么定?
一句话结论
Java PriorityQueue 默认小顶堆;传比较器决定堆序:a-b 小顶,b-a 大顶;对象按字段比较;比较器一致性影响堆行为。
概念解释
- 堆序键:比较结果。
- 默认自然序。
- 自定义字段。
原理流程
- 明确最值方向。
- 写比较器。
- 入队自动维护堆。
代码 / 示例
Queue<Integer> minHeap = new PriorityQueue<>();
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
常见误区
- 误区:比较器方向写反导致最值错误;正解:先确认要大顶还是小顶。
- 误区:整数比较用减法溢出;正解:大数用
Integer.compare。
追问
- Q:对象多字段排序? A:比较器按主次字段链式比较。
- Q:相等元素顺序? A:堆不保证稳定顺序。
02.3.2.4-017 堆/队列综合题有哪些边界用例?
一句话结论
空堆、单元素、全相同值、K=1、K=n、窗口大小 1、窗口等于数组长度、中位数偶数奇数、最小栈连续弹到空;验证判空与边界答案。
概念解释
- 空与最短。
- K 临界。
- 奇偶口径。
原理流程
- 空结构操作保护。
- K 取 1 与 n。
- 奇偶中位数与窗口边界。
代码 / 图示
K=1 / K=n
窗口 k=1 / k=n
中位数奇 / 偶
常见误区
- 误区:K=n 堆顶为第 n 大;正解:即最小值。
- 误区:单元素中位数两次取值;正解:按堆大小判断。
追问
- Q:窗口 k>n? A:按题目口径,通常 k≤n。
- Q:最小栈弹空? A:题目保证 pop 作用于非空栈。
02.3.2.4-018 堆的空间复杂度怎么算?
一句话结论
堆数组存全部入堆元素;Top-K 堆规模 K,空间 O(K);中位数双堆合计 O(n);建堆原地 O(1) 额外;节点引用与键占常数。
概念解释
- 堆规模:同时堆内元素。
- 双堆合计。
- 原地建堆。
原理流程
- 统计堆内最大元素数。
- 单元素常数。
- 双堆合并规模。
代码 / 图示
Top-K:O(K)
中位数:O(n)
原地建堆:O(1) 额外
常见误区
- 误区:Top-K 堆存全量;正解:固定 K。
- 误区:双堆各 O(n);正解:合计 O(n)。
追问
- Q:优先队列存对象额外开销? A:引用与对象本身另算。
- Q:流式只留 K? A:O(K) 空间,不保存历史。
02.3.2.4-019 哪些题适合用优先队列,哪些不适合?
一句话结论
适合:动态求最值、Top-K、合并有序序列、任务按优先级调度;不适合:需要有序遍历、按位置淘汰的窗口最值(单调队列更优)、频繁任意查找(平衡树更合适)。
概念解释
- 最值动态。
- 有序遍历需求。
- 位置淘汰。
原理流程
- 看核心操作:取最值。
- 看是否需全序。
- 看位置淘汰。
代码 / 图示
堆:最值、Top-K、合并 K 链
单调队列:窗口最值
平衡树:有序范围
常见误区
- 误区:窗口最大用堆也能 O(n);正解:堆淘汰过期需查找,O(n log n)。
- 误区:堆适合排序遍历;正解:堆内无序。
追问
- Q:合并 K 链表用堆? A:是,见 02.3.1.3。
- Q:任务调度按时间? A:优先队列按优先级,时间顺序另配轮次。
02.3.2.4-020 本知识域复杂度怎么汇报?
一句话结论
堆插入/取顶 O(log n),建堆 O(n);Top-K O(n log K)/O(K);中位数插入 O(log n)/取中位 O(1),空间 O(n);窗口单调队列 O(n)/O(k);最小栈 O(1)/O(n)。
概念解释
- 堆高 log n。
- 堆规模 K。
- 单调队列线性。
原理流程
- 标注堆操作次数与规模。
- 单调队列出入队计数。
- 辅助栈/堆空间分列。
代码 / 图示
堆操作:O(log n)
Top-K:O(n log K) / O(K)
窗口最大:O(n) / O(k)
最小栈:O(1) / O(n)
常见误区
- 误区:建堆 O(n log n);正解:自底向上 O(n)。
- 误区:单调队列 O(n log n);正解:元素出入各一次 O(n)。
追问
- Q:快速选择与堆法怎么选? A:离线求第 K 大可快速选择平均 O(n),流式用堆。
- Q:面试复杂度先讲哪个? A:先给主方法复杂度,再给对照方法口径。