双端队列与优先级队列（滑动窗口最大值 · Top K）

滑动窗口最大值（LeetCode 239）

单调递减双端队列（Deque）：队头始终是窗口最大值的下标。

int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();  // 存下标，单调递减

    for (int i = 0; i < n; i++) {
        // 1. 移除超出窗口的队头
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1)
            deque.pollFirst();
        // 2. 维护单调递减：移除所有小于当前值的队尾
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
            deque.pollLast();
        deque.offerLast(i);
        // 3. 窗口满 k 个时记录结果
        if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
    }
    return result;
}

前 K 个高频元素（堆做法）

int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);

    // 最小堆（保留频率最大的 k 个）
    PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        minHeap.offer(new int[]{e.getKey(), e.getValue()});
        if (minHeap.size() > k) minHeap.poll();  // 维持大小 k
    }

    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) result[i] = minHeap.poll()[0];
    return result;
}

数据流的第 K 大元素（LeetCode 703）

class KthLargest {
    private final PriorityQueue<Integer> minHeap;
    private final int k;

    KthLargest(int k, int[] nums) {
        this.k = k;
        minHeap = new PriorityQueue<>(k);  // 最小堆，容量 k
        for (int n : nums) add(n);
    }

    public int add(int val) {
        minHeap.offer(val);
        if (minHeap.size() > k) minHeap.poll();
        return minHeap.peek();  // 堆顶 = 第 k 大
    }
}

合并 K 个有序链表（LeetCode 23，堆做法）

ListNode mergeKLists(ListNode[] lists) {
    // 最小堆：按节点值排序
    PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
    for (ListNode head : lists) if (head != null) heap.offer(head);

    ListNode dummy = new ListNode(0), cur = dummy;
    while (!heap.isEmpty()) {
        cur.next = heap.poll();
        cur = cur.next;
        if (cur.next != null) heap.offer(cur.next);
    }
    return dummy.next;
}

丑数 II（LeetCode 264）

三指针 / 最小堆，维护丑数序列：

// 三指针（O(n)，推荐）
int nthUglyNumber(int n) {
    int[] ugly = new int[n];
    ugly[0] = 1;
    int p2 = 0, p3 = 0, p5 = 0;
    for (int i = 1; i < n; i++) {
        int next = Math.min(ugly[p2] * 2, Math.min(ugly[p3] * 3, ugly[p5] * 5));
        ugly[i] = next;
        if (next == ugly[p2] * 2) p2++;
        if (next == ugly[p3] * 3) p3++;
        if (next == ugly[p5] * 5) p5++;
    }
    return ugly[n - 1];
}

优先级队列 API 速查

PriorityQueue<Integer> minHeap = new PriorityQueue<>();           // 最小堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());  // 最大堆
PriorityQueue<int[]> custom  = new PriorityQueue<>((a, b) -> a[1] - b[1]);      // 自定义

minHeap.offer(x);   // 插入
minHeap.peek();     // 查看堆顶（不删）
minHeap.poll();     // 取出堆顶（删除）
minHeap.size();
minHeap.isEmpty();