LeetCode 460. LFU 缓存
目录
题目描述
题意分析
设计一个带容量上限的 LFU 缓存：
get(key)返回对应值或-1；put(key, value)插入或更新。容量满时淘汰「使用计数最小」的键；若最小计数有多个键并列，再按 LRU 规则淘汰其中最久未使用的那个——淘汰规则是两层的，这是与普通 LRU 缓存的本质区别。题目显式要求
get和put都以 $O(1)$ 平均时间完成，这直接排除了「淘汰时扫一遍找最小」的任何实现。细节信号：
get命中和put更新已有 key 都算一次「使用」，计数都要加一；边界上capacity可以为0，此时put应当直接无效；调用次数可达 $10^5$ 量级，常数也要控制。
解法：哈希表 + 频率链表
核心思路
问题关键：淘汰规则有两级——先找最低访问频次，再在同频节点中淘汰最久未使用者。若淘汰时遍历所有节点，
put会退化为 $O(n)$，无法满足题目的 $O(1)$ 平均复杂度要求。为什么选该解法：用
key → Node哈希表 $O(1)$ 找节点；用freq → 双向链表按频次分桶，每个桶按最近使用顺序排列，头部最新、尾部最旧；再维护minFreq直接定位淘汰桶。这样淘汰就是删除minFreq桶的尾节点。不变量：每个节点只属于与自身
freq对应的一个桶；每个桶内保持 LRU 顺序；minFreq始终指向当前最低的非空频次桶。访问只会让频次从f增至f + 1，所以旧桶若不是最低频，minFreq不变；若旧桶恰是最低频且迁移后为空，新的最低频只能是f + 1。插入新节点时频次固定为 1，直接令minFreq = 1。
get与更新已有 key 都复用一次“升频”操作：从旧桶摘除节点，修正minFreq，再把节点插到新桶头部。双向链表使用头尾哨兵，任意节点的删除和插入都是 $O(1)$。
解题步骤
- 初始化节点表、频次桶表和
minFreq；容量为 0 时，put直接返回。get(key)未命中返回-1；命中则执行升频，再返回节点值。put(key, value)命中时更新值并升频。更新也算一次访问，不能把频次重置为 1。- 插入新 key 前若容量已满，从
minFreq桶尾删除最旧节点，并从节点表同步删除。- 新节点以
freq = 1插入桶头，同时设置minFreq = 1。- 升频严格按“从旧桶摘除 → 旧桶为空时修正
minFreq→freq++→ 插入新桶头部”的顺序执行。例如容量为 2，执行
put(1,1)、put(2,2)、get(1)后，频次桶为1:[2]、2:[1]。此时put(3,3)必须淘汰频次最低的 key 2，而不是刚访问过的 key 1。
代码实现
class LFUCache {
private final int capacity;
private int minFreq;
private final Map<Integer, Node> nodes = new HashMap<>();
private final Map<Integer, DoubleList> lists = new HashMap<>();
public LFUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
Node node = nodes.get(key);
if (node == null) {
return -1;
}
increase(node);
return node.value;
}
public void put(int key, int value) {
if (capacity == 0) {
return;
}
Node node = nodes.get(key);
if (node != null) {
node.value = value;
increase(node);
return;
}
if (nodes.size() == capacity) {
DoubleList list = lists.get(minFreq);
Node removed = list.removeLast();
nodes.remove(removed.key);
if (list.isEmpty()) {
lists.remove(minFreq);
}
}
node = new Node(key, value);
nodes.put(key, node);
lists.computeIfAbsent(1, ignored -> new DoubleList()).addFirst(node);
minFreq = 1;
}
private void increase(Node node) {
int oldFreq = node.freq;
DoubleList oldList = lists.get(oldFreq);
oldList.remove(node);
if (oldList.isEmpty()) {
lists.remove(oldFreq);
if (oldFreq == minFreq) {
minFreq++;
}
}
node.freq++;
lists.computeIfAbsent(node.freq, ignored -> new DoubleList()).addFirst(node);
}
private static class Node {
int key;
int value;
int freq = 1;
Node pre;
Node next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private static class DoubleList {
private final Node head = new Node(0, 0);
private final Node tail = new Node(0, 0);
DoubleList() {
head.next = tail;
tail.pre = head;
}
void addFirst(Node node) {
node.next = head.next;
node.pre = head;
head.next.pre = node;
head.next = node;
}
void remove(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
Node removeLast() {
Node node = tail.pre;
remove(node);
return node;
}
boolean isEmpty() {
return head.next == tail;
}
}
}
type LFUCache struct {
capacity int
minFreq int
nodes map[int]*lfuNode
lists map[int]*lfuList
}
type lfuNode struct {
key int
value int
freq int
pre *lfuNode
next *lfuNode
}
type lfuList struct {
head *lfuNode
tail *lfuNode
}
func Constructor(capacity int) LFUCache {
return LFUCache{
capacity: capacity,
nodes: make(map[int]*lfuNode),
lists: make(map[int]*lfuList),
}
}
func (this *LFUCache) Get(key int) int {
node := this.nodes[key]
if node == nil {
return -1
}
this.increase(node)
return node.value
}
func (this *LFUCache) Put(key int, value int) {
if this.capacity == 0 {
return
}
if node := this.nodes[key]; node != nil {
node.value = value
this.increase(node)
return
}
if len(this.nodes) == this.capacity {
list := this.getList(this.minFreq)
removed := list.removeLast()
delete(this.nodes, removed.key)
if list.isEmpty() {
delete(this.lists, this.minFreq)
}
}
node := &lfuNode{key: key, value: value, freq: 1}
this.nodes[key] = node
this.getList(1).addFirst(node)
this.minFreq = 1
}
func (this *LFUCache) increase(node *lfuNode) {
oldFreq := node.freq
oldList := this.getList(oldFreq)
oldList.remove(node)
if oldList.isEmpty() {
delete(this.lists, oldFreq)
if oldFreq == this.minFreq {
this.minFreq++
}
}
node.freq++
this.getList(node.freq).addFirst(node)
}
func (this *LFUCache) getList(freq int) *lfuList {
if this.lists[freq] == nil {
head := &lfuNode{}
tail := &lfuNode{}
head.next = tail
tail.pre = head
this.lists[freq] = &lfuList{head: head, tail: tail}
}
return this.lists[freq]
}
func (list *lfuList) addFirst(node *lfuNode) {
node.next = list.head.next
node.pre = list.head
list.head.next.pre = node
list.head.next = node
}
func (list *lfuList) remove(node *lfuNode) {
node.pre.next = node.next
node.next.pre = node.pre
}
func (list *lfuList) removeLast() *lfuNode {
node := list.tail.pre
list.remove(node)
return node
}
func (list *lfuList) isEmpty() bool {
return list.head.next == list.tail
}
复杂度分析
- 时间复杂度：
get、put的平均时间复杂度均为 $O(1)$。每次只进行常数次哈希查找和链表摘插，minFreq也只做一步修正。- 空间复杂度：$O(\text{capacity})$。每个缓存项对应一个节点，空频次桶会被及时删除。
关键点总结
- 两张哈希表分别解决“按 key 定位”和“按频次分组”，桶内双向链表解决同频时的 LRU 淘汰。
minFreq能 $O(1)$ 更新的依据是频次只增不减：最低桶被升频搬空时只需加一，新节点插入时重置为 1。get和更新已有 key 都必须升频，统一复用increase可避免两条逻辑不同步。- 面试讲解顺序：先说两级淘汰规则，再给出三项不变量，最后解释
minFreq为什么不用扫描。
易错点总结
- 升频时必须先从旧桶删除，再修改
freq；否则会去错误的桶操作链表。- 只有“旧桶等于
minFreq且删除后为空”时才能minFreq++。例如桶1:[2,1]中访问 key 1 后，key 2 仍在频次 1，最低频不能变。- 淘汰和插入顺序不能反：容量为 1、旧节点频次为 2 时，若先插入并把
minFreq设为 1，会把新节点自己淘汰。- 淘汰节点时要同时从链表和节点表删除；空桶也应删除，否则空间会随历史频次增长。
- 新节点必须令
minFreq = 1；capacity = 0必须直接返回，避免从不存在的桶中淘汰。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 146. LRU 缓存 | 中等 | 单层「最近使用」淘汰，本题的前置与退化情形 |
| 432. 全 O(1) 的数据结构 | 困难 | 同款计数分桶 + 桶间迁移，桶本身也串成双向链表 |
| LCR 031. LRU 缓存 | 中等 | 146 的镜像题，练哈希表 + 双向链表的标准组合 |
| 面试题 16.25. LRU 缓存 | 中等 | 同为 LRU 设计，可对比内置有序结构与手写链表的取舍 |