罗罗编程学习记录
本页内容 展开查看

02.3.2.4 优先队列、堆与栈队列综合

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.2 栈与队列、单调栈

02.3.2.4-001 堆是什么结构?

一句话结论

堆是满足堆序的完全二叉树:大顶堆父节点 ≥ 子节点,小顶堆父节点 ≤ 子节点;堆顶为最值;通常用数组存储,支持插入与取最值 O(log n)。

概念解释

  • 堆序:父子大小关系。
  • 完全二叉树:层内填满。
  • 最值:堆顶。

原理流程

  1. 数组表示二叉树。
  2. 插入后上浮维护堆序。
  3. 取堆顶后下沉维护。

代码 / 图示

大顶堆:
      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;完全二叉树紧凑存数组,无空指针;边界下标越界需判断。

概念解释

  • 层序编号。
  • 父子公式。
  • 数组连续存储。

原理流程

  1. 根下标 0。
  2. 按层序填数组。
  3. 公式定位父子。

代码 / 图示

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) 比较与交换;大顶堆上浮到父更大为止。

概念解释

  • 末尾插入。
  • 上浮:与父交换。
  • 堆序恢复。

原理流程

  1. 追加末尾。
  2. 与父比较。
  3. 违反则交换,指针上移。

代码 / 示例

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);大顶堆选较大孩子交换。

概念解释

  • 堆顶移除。
  • 末尾补位。
  • 下沉恢复堆序。

原理流程

  1. 堆顶 = 末尾元素。
  2. size 减一。
  3. 选合适孩子比较交换,继续下沉。

代码 / 示例

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);整体线性。

概念解释

  • 自底向上。
  • 层代价:低层节点多但浅。
  • 级数求和收敛。

原理流程

  1. 从最后一个非叶子节点向前。
  2. 逐个下沉。
  3. 求和各层下沉步数。

代码 / 图示

第 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。
  • 堆顶为当前边界。
  • 超界替换。

原理流程

  1. 先放 K 个入堆。
  2. 后续元素与堆顶比较。
  3. 更优则替换下沉。

代码 / 示例

// 前 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 个最大中的最小。
  • 小顶堆堆顶。
  • 流式与离线均可。

原理流程

  1. 堆维护 K 大。
  2. 新元素超堆顶则替换。
  3. 堆顶为答案。

代码 / 示例

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。

原理流程

  1. 新元素先入左大顶堆。
  2. 左堆顶移右堆,保证右半 ≥ 左半。
  3. 不平衡则回迁。

代码 / 示例

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) 空间。

概念解释

  • 递减队列:队首最大。
  • 队尾淘汰小值。
  • 队首淘汰过期。

原理流程

  1. 新元素入队前弹队尾更小。
  2. 队首过期弹出。
  3. 窗口形成后队首为答案。

代码 / 示例

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 单调队列模板有哪些固定步骤?

一句话结论

① 队首淘汰过期下标;② 队尾维护单调方向弹出破坏顺序元素;③ 当前下标入队;④ 窗口形成后取队首;四步对最大/最小通用,只改比较方向。

概念解释

  • 过期:下标 < 窗口左界。
  • 单调:队首最值。
  • 入队:队尾挂接。

原理流程

  1. 清过期队首。
  2. 清队尾破坏单调者。
  3. 入队。
  4. 记录队首。

代码 / 图示

for i:
  队首过期 → 出队首
  队尾劣于当前 → 出队尾
  入队尾
  窗口满 → 答案队首

常见误区

  • 误区:先入队再清过期;正解:先清过期再维护队尾。
  • 误区:队尾弹出条件写反;正解:最大用 <= 弹小,最小用 >= 弹大。

追问

  • Q:单调队列与单调栈区别? A:队列两端操作,栈只一端。
  • Q:每个元素入队出队几次? A:各一次,O(n)。

02.3.2.4-011 最小栈(LC 155)怎么设计?

一句话结论

主栈存全部元素,辅助栈同步存当前最小值;push 时辅助栈压入与栈顶较小值;pop 两栈同步弹出;getMin 取辅助栈顶;O(1) 各操作,空间 O(n)。

概念解释

  • 主栈:元素。
  • 辅助栈:对应最小值。
  • 同步压弹。

原理流程

  1. push:主栈压值,辅助栈压 min(值, 辅助栈顶)。
  2. pop:两栈同弹。
  3. 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 最小栈辅助栈为什么要同步压最小值?

一句话结论

若只压新的更小值,弹出当前最小值后,辅助栈顶丢失之前的次小值;同步压入“到当前为止的最小值”,每弹一层都有对应最小;栈与辅助栈一一对应。

概念解释

  • 一一对应:每层一个最小值。
  • 弹栈恢复。
  • 重复值保留。

原理流程

  1. 每层记录当前最小。
  2. 弹出后回到上一层最小。
  3. 辅助栈长度等于主栈。

代码 / 图示

主栈:  5 3 7 2
辅助:  5 3 3 2

常见误区

  • 误区:辅助栈只存递减最小值;正解:非更小元素也要压当前最小。
  • 误区:弹主栈后辅助栈滞后;正解:同步弹出。

追问

  • Q:差值法怎么省空间? A:栈存与最小值的差,更新最小值,细节按实现。
  • Q:最大栈同理吗? A:方向反转即可。

02.3.2.4-013 栈与队列综合设计题怎么拆解?

一句话结论

先明确接口语义(栈 LIFO / 队列 FIFO / 最值),再选基础结构(数组/链表/双栈/双堆),最后核对每个操作的复杂度与边界;常见组合:两栈队列、两队列栈、最小栈、双堆中位数。

概念解释

  • 语义:操作顺序。
  • 结构:底层载体。
  • 复杂度:操作代价。

原理流程

  1. 列接口与顺序要求。
  2. 选模拟结构。
  3. 验证边界与复杂度。

代码 / 图示

顺序要求 → 栈/队列
最值要求 → 辅助栈/堆

常见误区

  • 误区:上来就写代码不明确语义;正解:先定出队/出栈规则。
  • 误区:忽略淘汰与同步;正解:双结构状态一致。

追问

  • Q:设计题要考虑扩容吗? A:按题目容量要求,固定或动态说明。
  • Q:线程安全? A:题目未要求时按单线程实现。

02.3.2.4-014 堆与红黑树、排序怎么对比?

一句话结论

堆 O(log n) 插入、取堆顶 O(log n),但不支持有序遍历与任意查找;红黑树 O(log n) 增删查且有序;全量排序 O(n log n);Top-K 与最值场景堆更轻量。

概念解释

  • 堆:只维护最值。
  • 平衡树:全序维护。
  • 排序:一次性全量有序。

原理流程

  1. 看是否需要有序遍历。
  2. 看是否只需最值。
  3. 选结构。

代码 / 图示

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)。
  • 取顶交换。
  • 下沉恢复。

原理流程

  1. 原地建大顶堆。
  2. 堆顶换末尾。
  3. 规模减一,下沉堆顶。

代码 / 图示

大顶堆 → 最大值在根
交换到末尾 → 剩余堆下沉

常见误区

  • 误区:堆排序稳定;正解:交换跨距大,不稳定。
  • 误区:建堆 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 大顶;对象按字段比较;比较器一致性影响堆行为。

概念解释

  • 堆序键:比较结果。
  • 默认自然序。
  • 自定义字段。

原理流程

  1. 明确最值方向。
  2. 写比较器。
  3. 入队自动维护堆。

代码 / 示例

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 临界。
  • 奇偶口径。

原理流程

  1. 空结构操作保护。
  2. K 取 1 与 n。
  3. 奇偶中位数与窗口边界。

代码 / 图示

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) 额外;节点引用与键占常数。

概念解释

  • 堆规模:同时堆内元素。
  • 双堆合计。
  • 原地建堆。

原理流程

  1. 统计堆内最大元素数。
  2. 单元素常数。
  3. 双堆合并规模。

代码 / 图示

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、合并有序序列、任务按优先级调度;不适合:需要有序遍历、按位置淘汰的窗口最值(单调队列更优)、频繁任意查找(平衡树更合适)。

概念解释

  • 最值动态。
  • 有序遍历需求。
  • 位置淘汰。

原理流程

  1. 看核心操作:取最值。
  2. 看是否需全序。
  3. 看位置淘汰。

代码 / 图示

堆:最值、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。
  • 单调队列线性。

原理流程

  1. 标注堆操作次数与规模。
  2. 单调队列出入队计数。
  3. 辅助栈/堆空间分列。

代码 / 图示

堆操作: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:先给主方法复杂度,再给对照方法口径。