专题 24进阶速览：单调队列、设计题与抽样

24.1单调队列：滑动窗口最大值（困难，力扣 239）

困难 核心：Deque 存下标 · 候选集淘汰

题意：给你一个数组 nums 和窗口大小 k，窗口从最左滑到最右，求每个窗口里的最大值，返回数组。例：nums=[1,3,-1,-3,5,3,6,7], k=3 → 各窗口最大为 [3,3,5,5,6,7]。

思路推导

第一步，暴力与 naive 滑窗的代价。每滑一次重新找最大是 O(k)，总 O(nk)。能不能每个元素只处理一次？关键是维护一个「当前窗口候选最大值集合」。

第二步，核心直觉——「候选集淘汰」。用双端队列 Deque 存下标（必须存下标，才能判断它是否滑出窗口），且保持队列里下标对应的数值从队头到队尾严格递减（队头永远是当前窗口最大）。

第三步，入队时从队尾淘汰。当新元素 nums[i] 要进窗口，它比队尾元素大时，队尾那些元素「这辈子都不可能再成为最大值了」——因为 nums[i] 更晚进、也更晚出，只要它还在窗口，队尾那些更小的就永远被压着。所以从队尾不断弹出比 nums[i] 小的，再把 i 压入。这样队头始终是最大值。

第四步，出队头判过期。每步检查队头下标是否 ≤ i - k（已滑出左边界），是则弹出。窗口形成后（i >= k-1），队头就是当前窗口最大值，记录。

第五步，与单调栈对比（承接 专题 06）。单调栈是「只从栈顶进、只从栈顶出」（处理「下一个更大元素」）；单调队列是「从队尾进、队头队尾都能出」（队头出是因为过期、队尾出是因为被淘汰）。一个只进不出端不同，用途也不同。

参考代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();   // 存下标，队头=当前最大
        for (int i = 0; i < n; i++) {
            // ① 队尾淘汰：弹出所有比 nums[i] 小的（它们永无出头之日）
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }
            dq.offerLast(i);                       // ② 下标入队尾
            // ③ 队头过期就弹出（滑出窗口左边界）
            if (dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }
            // ④ 窗口形成后，队头即当前窗口最大值
            if (i >= k - 1) {
                ans[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        return ans;
    }
}

复杂度

O(n) 时间（每个下标最多入队一次、出队一次），O(k) 空间（队列长度不超过窗口）。把 O(nk) 压到 O(n)，是单调队列的招牌应用。

24.2LRU 缓存：哈希表 + 双向链表（中等，力扣 146）

中等 核心：HashMap + 自制双向链表

题意：设计一个数据结构，支持：get(key) 取值（不存在返回 -1）、put(key, value) 写入；容量满时淘汰最久没用过的（LRU = Least Recently Used）。两个操作都要 O(1)。例：容量 2，依次 put(1,1), put(2,2), get(1), put(3,3) → 此时淘汰 key2（最久未用），再 get(2) 返回 -1。

思路推导

第一步，为什么单向链表不够。要 O(1) 删除「任意节点」（比如某个 key 被访问后要从原位置摘下、移到头部），需要知道它的前驱。单向链表找前驱要遍历，破坏 O(1)。所以必须用双向链表：每个节点有 prev/next，删除/插入都 O(1)。

第二步，组合两个结构。HashMap<key, Node> 负责按 key 秒查节点（O(1) 定位）；双向链表负责维护使用顺序——最近用的放头部，最久未用的在尾部。淘汰时删尾节点，并从 map 移除。

第三步，哨兵节点简化边界。链表头尾各放一个「 dummy 哨兵」（head、tail），这样真正的元素永远在中间，addToHead / removeNode 不用特判空指针，代码干净很多。

第四步，get / put 的套路。 get：map 查到 → 把节点移到头部（删原位置 + 加到头）并返回值；查不到返回 -1。 put：若 key 已存在 → 更新值并移到头部（注意不是新增！见坑）；若不存在 → 新建节点加到头部，map 放入；若超容量 → 删尾部节点并从 map 移除。

参考代码（完整可提交）

class LRUCache {
    // 双向链表节点
    class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }

    private int capacity, size = 0;
    private Map<Integer, Node> map = new HashMap<>();
    private Node head, tail;               // 哨兵，head 最近、tail 最久

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(0, 0); tail = new Node(0, 0);
        head.next = tail; tail.prev = head; // 串起两个哨兵
    }

    // 把节点 x 加到 head 之后（最新位置）
    private void addToHead(Node x) {
        x.prev = head; x.next = head.next;
        head.next.prev = x; head.next = x;
    }
    // 从链表中摘除 x
    private void remove(Node x) {
        x.prev.next = x.next; x.next.prev = x.prev;
    }
    // 把已有节点移到头部（先删后加）
    private void moveToHead(Node x) {
        remove(x); addToHead(x);
    }

    public int get(int key) {
        Node x = map.get(key);
        if (x == null) return -1;
        moveToHead(x);                     // 访问过 → 变最新
        return x.val;
    }

    public void put(int key, int value) {
        Node x = map.get(key);
        if (x != null) {                   // 已存在：更新并移到头部（非新增！）
            x.val = value;
            moveToHead(x);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            addToHead(node);
            size++;
            if (size > capacity) {          // 超容量：淘汰最久（尾前节点）
                Node old = tail.prev;
                remove(old);
                map.remove(old.key);
                size--;
            }
        }
    }
}

复杂度

get / put 均 O(1)（哈希定位 + 链表常数操作），空间 O(capacity)。这是面试设计题的标杆模板。

24.3LFU 缓存思路（困难，力扣 460，选学）

困难 核心：频率桶 + 每桶内 LRU 选学

它解决什么：LRU 淘汰「最久没用」的；LFU（Least Frequently Used）淘汰「使用次数最少」的——若多个都用得少，再比谁更久没用。适用于「热点数据应常驻」的场景。

设计骨架（不给完整实现）

关键难点是既要按频率分层、又要同频内按时间排序，且所有操作 O(1)。经典骨架：

• 频率桶：用一个 Map<freq, 双向链表>，每个频率值对应一个双向链表，链表内按 LRU 顺序（头新尾旧）排该频率下的 key；
• 每个 key 的记录：Map<key, (value, freq)> 存值与当前频率；
• minFreq 维护：单独记录「当前最小频率」，淘汰时直接去 minFreq 对应的链表删尾节点（最久未用且频率最低）。get/put 命中后把节点从旧频率桶移到新频率桶头部，若旧桶空且恰是 minFreq 则 minFreq++。

24.4链表随机节点：蓄水池抽样（中等，力扣 382）

中等 核心：第 i 个以 1/i 概率替换

题意：给一个单向链表（长度未知、可能极大，不允许先遍历计数再随机），要求实现 getRandom()：等概率返回链表中的任一节点值。多次调用，每个节点被返回的概率相同。

思路推导

第一步，为什么不能直接随机下标。单向链表不能 O(1) 按 index 取，且题目常隐含「数据流式到来、总长度未知或太大」。必须先遍历一遍才能知道长度，但那样 getRandom 每次都要重遍历，太慢；若数据无限流更不可能。

第二步，蓄水池抽样思想——边走边定。只遍历一次，一边走一边维护「当前候选」。规则：

• 第 1 个节点，直接选它（概率 1）；
• 第 2 个节点，以 1/2 的概率替换候选；
• 第 3 个节点，以 1/3 的概率替换候选；
• ……第 i 个节点，以 1/i 的概率替换候选。

第三步，为什么这样能保证等概率（一句话直觉）。每个节点「最终存活」的概率 = 「它被选入的概率」×「之后所有节点都没把它换掉的概率」= (1/i) × (i/(i+1)) × ((i+1)/(i+2)) × … × ((n-1)/n) = 1/n。望远镜式约分后，每个节点恰好 1/n。妙在不需要事先知道 n。

第四步，循环从 i=1 还是 i=0。若用「已遍历计数 cnt」，第一个节点 cnt=1 概率 1/1 直接选；之后 cnt 递增，第 cnt 个以 1/cnt 替换。注意 cnt 从 1 开始（不是 0），否则会出现除以 0 或概率错（见 24.6 节坑三）。

参考代码

class Solution {
    ListNode head;
    Random rand = new Random();

    public Solution(ListNode head) { this.head = head; }

    public int getRandom() {
        int ans = 0;                  // 当前候选值
        int cnt = 0;                  // 已遍历节点数（从 1 开始）
        ListNode p = head;
        while (p != null) {
            cnt++;                    // 第 cnt 个节点
            // 以 1/cnt 的概率把候选替换为当前节点
            if (rand.nextInt(cnt) == 0) {   // 等价于 Math.random() < 1.0/cnt
                ans = p.val;
            }
            p = p.next;
        }
        return ans;
    }
}

复杂度

O(n) 时间（每次 getRandom 遍历一遍链表），O(1) 额外空间。代价是每次调用都走一遍，但换来了「不依赖总长、等概率」的能力，是流式抽样的标配。

24.5树状数组与线段树是什么（概念）

核心：单点改 + 区间和 竞赛向

它们解决什么：一类「动态」问题——数组会频繁单点修改，又频繁问「某段区间的和 / 最值」。朴素做法：修改 O(1) 但区间求和 O(n)，或前缀和 O(1) 查询但修改 O(n)。树状数组（Fenwick Tree）和线段树（Segment Tree）把两者都压到 O(log n)。

两个思想的直觉（不写实现）

① 树状数组 = 「前缀和的分块倍增」。它不存完整前缀和，而是把下标按「二进制最低位 1 的位置」分块，每个节点管一段长度为 2ᵏ 的区间。修改时只更新「覆盖到它的几个块」，查询前缀和时把「几个不重叠的块」拼起来，都是沿着 lowbit 跳转，O(log n)。优点：代码极短、常数小；缺点：主要擅长「前缀和 / 单点改」，区间最值不自然。

② 线段树 = 「区间的二分树」。把区间 [1, n] 不断对半拆成左右子区间，建成一棵二叉树，每个节点存对应区间的聚合值（和 / 最大 / 最小皆可）。修改和查询都沿树下钻到 O(log n) 个节点。优点：通用，区间最值、区间修改都能做；缺点：代码比树状数组长。

怎么选、面试到什么程度

24.6本专题常见坑

24.7自测题