单调队列与优先队列：滑动窗口最大值

暴力解法的瓶颈在哪里

滑动窗口最大值（239）：数组 nums 和窗口大小 k，窗口从左往右每次滑动一格，返回每个位置窗口内的最大值。例如 [1,3,-1,-3,5,3,6,7]，k=3，输出 [3,3,5,5,6,7]。

暴力做法对每个窗口重新求一次最大值，O(nk)。当 k ≈ n/2 时就是 O(n²) 起步，LeetCode 上 n 达到 10⁵ 会直接超时。

瓶颈的根源：相邻两个窗口有 k-1 个元素是重叠的，但暴力完全丢弃了上一窗口的比较结果。观察滑动过程，其实只有两种信息变化：

窗口最左边的元素离开了，它可能曾是最大值；
一个新元素进入了，它可能成为新的最大值。

如果维护的容器能在这两种事件发生时以 O(1) 或 O(log n) 更新"当前窗口最大值"，整体就是 O(n) 或 O(n log n)。这就引出两种武器：单调队列（O(n)）和优先队列（O(n log n)）。

单调队列：队头最大，队尾淘汰

单调队列不是 Java 自带的结构，而是"普通队列 + 两条纪律"组成的自定义容器，保持队内元素从队头到队尾单调递减：

纪律一（队尾淘汰）：新元素入队前，把队尾所有小于等于它的元素弹出。被弹的元素永远不会比新元素晚离开窗口，值又不比它大——它们此后绝无可能成为窗口最大值，淘汰是永久且安全的；
纪律二（队头出窗）：每次取答案前，检查队头是否已经滑出窗口（存下标才能判断），出了就弹出。

于是队头永远是当前窗口的最大值。用 Deque 实现，队尾用 pollLast/offerLast，队头用 pollFirst/peekFirst：

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] res = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>(); // 存下标，方便判断出窗
 
    for (int i = 0; i < n; i++) {
        // 纪律一：队尾所有小于当前值的元素被永久淘汰
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);                      // 当前元素进队尾
 
        // 纪律二：队头越界（下标 <= i-k 说明已滑出窗口）则弹出
        if (deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }
        // 窗口成形后，队头下标对应的值就是最大值
        if (i >= k - 1) {
            res[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return res;
}

手动模拟 [1,3,-1,-3,5,3,6,7]，k=3，重点看 5 进入时：队内是 [3,-1,-3]（下标 1,2,3），5 把 -1、-3 从队尾挤掉，再和 3 比——3 比 5 小也被挤掉，队内只剩 [5]。被挤掉的 3 虽然还没滑出窗口，但它已经没有价值：论值它更小，论资历它更老，两头都不占。

一个常被追问的点：为什么可以存下标而不是值？ 因为出窗判断必须知道元素的"年龄"（位置），值本身无法回答"你还属于当前窗口吗"。这也是为什么纪律一的比较要写成 nums[deque.peekLast()] <= nums[i]。

每个元素至多入队一次、出队一次，总操作数 ≤ 2n，均摊 O(n)。这是"均摊"分析的又一次亮相（和 232 的双栈倒灌同一个套路）。

前 K 个高频元素（347）：堆登场

题目：返回数组中出现频率前 k 高的元素。例如 [1,1,1,2,2,3]，k=2，输出 [1,2]。数据范围允许 O(n log n)，且要求优于 O(n log n) 的暴力排序（对全部元素按频率排序是 O(n log n) 起步，但对 n 个元素全排序太浪费——我们只要前 k 个）。

第一步（两种思路共用）：HashMap 统计每个数字的频率，问题转化为"从若干 (数字, 频率) 对里选频率最高的 k 个"。

思路 A：小顶堆，大小恒为 k。用 (频率, 数字) 对建堆，比较器按频率升序——堆顶是当前 k 个候选里频率最低的，新元素比它高就把堆顶挤掉：

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : nums) count.merge(x, 1, Integer::sum);
 
    // 小顶堆按频率升序，堆顶是 k 个候选中频率最低的"门槛"
    PriorityQueue<int[]> heap = new PriorityQueue<>(
        (a, b) -> a[1] - b[1]
    );
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        if (heap.size() < k) {
            heap.offer(new int[]{e.getKey(), e.getValue()});
        } else if (e.getValue() > heap.peek()[1]) {
            heap.poll();                          // 淘汰当前门槛
            heap.offer(new int[]{e.getKey(), e.getValue()});
        }
    }
    int[] res = new int[k];
    for (int i = 0; i < k; i++) res[i] = heap.poll()[0];
    return res;
}

为什么求前 k 大反而用小顶堆？ 这是本题最大的思维关：堆里只需保留"k 个最强候选 + 一个最低门槛"，用小顶堆把门槛顶在堆顶，新元素和门槛比较即可决定进出，成本 O(log k)。若用大顶堆，虽然堆顶就是答案，但要容纳全部 n 个不同元素，成本 O(log n)，反而更差。

思路 B：桶排序，O(n)。频率的取值范围有限（1 到 n），直接按频率开桶：

public int[] topKFrequentBucket(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : nums) count.merge(x, 1, Integer::sum);
 
    // buckets[f] = 频率恰为 f 的所有数字；频率最高 n
    List<Integer>[] buckets = new List[nums.length + 1];
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        int f = e.getValue();
        if (buckets[f] == null) buckets[f] = new ArrayList<>();
        buckets[f].add(e.getKey());
    }
 
    int[] res = new int[k];
    int idx = 0;
    // 从高频桶往低频桶收集，凑满 k 个即止
    for (int f = buckets.length - 1; f >= 0 && idx < k; f--) {
        if (buckets[f] != null) {
            for (int x : buckets[f]) {
                res[idx++] = x;
                if (idx == k) break;
            }
        }
    }
    return res;
}

桶排序把"比较"变成了"下标寻址"，计频 O(n)、收集 O(n)，总 O(n)。代价是频率分布极稀疏时数组浪费空间——刷题场景下这不算问题。

单调队列 vs 优先队列：怎么选

两种结构都在动态维护"最值"，但适用场景不同，选型看三个问题：

对比维度	单调队列	优先队列（堆）
维护对象	滑动窗口内的最值	动态集合的全局最值
出队依据	元素位置（滑出窗口）	元素优先级
单次操作	均摊 O(1)（每个元素进出各一次）	O(log n)
元素能否被"永久淘汰"	能（见纪律一的分析）	能，但理由是优先级而非过期
典型题目	239 滑动窗口最大值	347 前 K 个高频、215 数组第 k 大
Java 载体	`Deque`（自定义纪律）	`PriorityQueue`（自定义比较器）

一句话决策：最值的"有效期"由位置决定 → 单调队列；由大小/频率等属性决定 → 堆。窗口滑动时元素会"过期"，单调队列抓住这一点直接物理删除；而"前 k 高频"里元素的寿命只由频率排名决定，没有位置过期一说，堆是自然选择。

再补一条：如果题目里"最值候选"能像 239 那样被证明"永无翻身之日"，就优先考虑单调队列这种 O(n) 方案；只有当淘汰理由不充分时，才退而求其次用堆，接受一个 log 的代价。

LeetCode 题单

题号	题名	一句话考点
239	滑动窗口最大值	单调递减队列：队尾淘汰弱者、队头出窗
347	前 K 个高频元素	计频 + 大小为 k 的小顶堆，或桶排序 O(n)
215	数组中的第K个最大元素	快速选择或小顶堆，与 347 同族
703	数据流中的第 K 大元素	维持大小为 k 的小顶堆，堆顶即答案
239 变形	滑动窗口最小值	队内改维护递增，其余逻辑对称
155	最小栈	辅助栈同步维护最小值，退化为"栈 + 副本"

参考

代码随想录 · 栈与队列专题