LeetCode 460：LFU 缓存

LeetCode 460：LFU 缓存

问题本质：理解 LFU 策略

LFU（Least Frequently Used）缓存的核心是 优先淘汰“使用次数最少”的键；若存在“使用次数相同”的键，则淘汰最久未使用的那个（兼顾 LRU 特性）。

要实现高效的 get 和 put（均要求 O(1) 平均时间），需解决两个核心问题：

1. 快速更新键的使用次数；
2. 快速找到“使用次数最少且最久未使用”的键。

数据结构设计：三层架构

1. 节点类（Node）

存储键、值、使用次数，以及双向链表的前驱和后继指针（支持 O(1) 插入/删除）：

class Node { int key; int value; int count; // 使用次数 Node prev; Node next; public Node(int key, int value) { this.key = key; this.value = value; this.count = 1; // put 操作初始次数为 1 }}

2. 双向链表（DoubleLinkedList）

维护同一使用次数下的键，按访问顺序排列（队首是最久未使用，队尾是最近使用）：

class DoubleLinkedList { Node head; // 哨兵头节点 Node tail; // 哨兵尾节点 int size; // 链表长度 public DoubleLinkedList() { head = new Node(-1, -1); tail = new Node(-1, -1); head.next = tail; tail.prev = head; size = 0; } // 在链表尾部添加节点（最近使用） public void addLast(Node node) { node.prev = tail.prev; node.next = tail; tail.prev.next = node; tail.prev = node; size++; } // 删除指定节点（O(1)，需节点自身的前驱/后继指针） public void remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; size--; } // 删除队首节点（最久未使用，O(1)） public Node removeFirst() { if (size == 0) return null; Node first = head.next; remove(first); return first; }}

3. 三层映射关系

• keyToNode：键 → 节点（快速定位节点，O(1)）。
• countToMap：使用次数 → 双向链表（快速分组管理同次数的键，O(1) 操作链表）。
• counts：有序存储所有存在的使用次数（基于 TreeSet，快速获取最小次数，O(log n)）。

核心操作解析

1. get 操作：更新使用次数

public int get(int key) { if (!keyToNode.containsKey(key)) return -1; // 键不存在 Node node = keyToNode.get(key); int oldCount = node.count; // 1. 从旧次数的链表中移除节点 DoubleLinkedList oldList = countToMap.get(oldCount); oldList.remove(node); if (oldList.size == 0) { // 链表空则移除次数 countToMap.remove(oldCount); counts.remove(oldCount); } // 2. 更新节点次数，加入新次数的链表 node.count++; int newCount = node.count; countToMap.putIfAbsent(newCount, new DoubleLinkedList()); countToMap.get(newCount).addLast(node); counts.add(newCount); // 维护次数的有序性 return node.value;}

2. put 操作：插入或更新键值

public void put(int key, int value) { if (capacity == 0) return; // 容量为 0 特殊处理 if (keyToNode.containsKey(key)) { // 键已存在：更新值 + 同 get 逻辑更新次数 Node node = keyToNode.get(key); node.value = value; // 以下逻辑同 get 操作，复用次数更新逻辑 int oldCount = node.count; DoubleLinkedList oldList = countToMap.get(oldCount); oldList.remove(node); if (oldList.size == 0) { countToMap.remove(oldCount); counts.remove(oldCount); } node.count++; int newCount = node.count; countToMap.putIfAbsent(newCount, new DoubleLinkedList()); countToMap.get(newCount).addLast(node); counts.add(newCount); return; } // 键不存在：需插入新节点 if (size == capacity) { // 容量已满，淘汰最小次数的最久未使用节点 int minCount = counts.first(); // 获取当前最小次数 DoubleLinkedList minList = countToMap.get(minCount); Node removed = minList.removeFirst(); // 淘汰队首（最久未使用） keyToNode.remove(removed.key); size--; if (minList.size == 0) { // 链表空则移除次数 countToMap.remove(minCount); counts.remove(minCount); } } // 插入新节点（次数初始为 1） Node newNode = new Node(key, value); keyToNode.put(key, newNode); int newCount = 1; countToMap.putIfAbsent(newCount, new DoubleLinkedList()); countToMap.get(newCount).addLast(newNode); counts.add(newCount); size++;}

关键设计细节

1. 双向链表的作用：
   同一使用次数下的键按访问顺序维护，队首是最久未使用，保证淘汰时直接取队首，O(1) 时间。

2. TreeSet 维护次数有序性：
   快速获取当前最小使用次数（counts.first()），确保淘汰逻辑的高效性。

3. 边界处理：

   • 容量为 0 时，put 直接返回。
   • 链表为空时，及时移除对应的次数，避免无效查询。

复杂度分析

• 时间复杂度：

  • get 和 put 的核心操作（哈希表、双向链表）均为 O(1)；
  • TreeSet 的插入/删除为 O(log k)（k 是不同使用次数的数量，远小于操作次数）。
    整体平均时间复杂度接近 O(1)，满足题目要求。

• 空间复杂度：
  存储 n 个键，空间复杂度为 O(n)（n ≤ 2×10⁵，符合约束）。

示例验证（以题目示例为例）

输入：

[\"LFUCache\",\"put\",\"put\",\"get\",\"put\",\"get\",\"get\",\"put\",\"get\",\"get\",\"get\"][[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]

核心流程解析：

1. 初始化：容量 2，空缓存。
2. put(1,1)：新节点入队，次数 1，countToMap[1] 链表包含 1。
3. put(2,2)：新节点入队，次数 1，countToMap[1] 链表包含 2（队尾，最近使用）。
4. get(1)：节点 1 次数增至 2，从 countToMap[1] 移除，加入 countToMap[2]。
5. put(3,3)：容量已满，淘汰 counts.first()=1 对应的链表（节点 2，最久未用），插入 3（次数 1）。
6. 后续操作类似，最终输出符合题目预期。

完整代码（Java）

import java.util.HashMap;import java.util.Map;import java.util.TreeSet;class Node { int key; int value; int count; Node prev; Node next; public Node(int key, int value) { this.key = key; this.value = value; this.count = 1; }}class DoubleLinkedList { Node head; Node tail; int size; public DoubleLinkedList() { head = new Node(-1, -1); tail = new Node(-1, -1); head.next = tail; tail.prev = head; size = 0; } public void addLast(Node node) { node.prev = tail.prev; node.next = tail; tail.prev.next = node; tail.prev = node; size++; } public void remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; size--; } public Node removeFirst() { if (size == 0) return null; Node first = head.next; remove(first); return first; }}public class LFUCache { private int capacity; private int size; private Map<Integer, Node> keyToNode; private Map<Integer, DoubleLinkedList> countToMap; private TreeSet<Integer> counts; public LFUCache(int capacity) { this.capacity = capacity; this.size = 0; keyToNode = new HashMap<>(); countToMap = new HashMap<>(); counts = new TreeSet<>(); } public int get(int key) { if (!keyToNode.containsKey(key)) { return -1; } Node node = keyToNode.get(key); int oldCount = node.count; // 移除旧次数的链表节点 DoubleLinkedList oldList = countToMap.get(oldCount); oldList.remove(node); if (oldList.size == 0) { countToMap.remove(oldCount); counts.remove(oldCount); } // 更新次数并加入新链表 node.count++; int newCount = node.count; countToMap.putIfAbsent(newCount, new DoubleLinkedList()); countToMap.get(newCount).addLast(node); counts.add(newCount); return node.value; } public void put(int key, int value) { if (capacity == 0) { return; } if (keyToNode.containsKey(key)) { Node node = keyToNode.get(key); node.value = value; // 处理旧次数 int oldCount = node.count; DoubleLinkedList oldList = countToMap.get(oldCount); oldList.remove(node); if (oldList.size == 0) { countToMap.remove(oldCount); counts.remove(oldCount); } // 更新新次数 node.count++; int newCount = node.count; countToMap.putIfAbsent(newCount, new DoubleLinkedList()); countToMap.get(newCount).addLast(node); counts.add(newCount); return; } // 容量已满，淘汰最小次数的最久未使用节点 if (size == capacity) { int minCount = counts.first(); DoubleLinkedList minList = countToMap.get(minCount); Node removed = minList.removeFirst(); keyToNode.remove(removed.key); size--; if (minList.size == 0) { countToMap.remove(minCount); counts.remove(minCount); } } // 插入新节点 Node newNode = new Node(key, value); keyToNode.put(key, newNode); int newCount = 1; countToMap.putIfAbsent(newCount, new DoubleLinkedList()); countToMap.get(newCount).addLast(newNode); counts.add(newCount); size++; }}

总结：LFU 的设计哲学

通过 “哈希表 + 双向链表 + 有序集合” 的三层架构，LFU 缓存实现了：

• 快速定位（键 → 节点）；
• 同次数分组（次数 → 链表，维护访问顺序）；
• 最小次数快速获取（有序集合，支持淘汰策略）。

这种设计高效平衡了时间和空间复杂度，是处理频率优先 + 时序优先缓存问题的经典方案。