LeetCode 146. LRU 缓存
目录
题目描述
题意分析
设计一个固定容量的 LRU（Least Recently Used，最近最少使用）缓存，支持两个操作：
get(key)命中返回值、未命中返回-1；put(key, value)插入或更新，若插入后超出容量则逐出最久未使用的那个 key。题目明确要求两个操作都是平均 $O(1)$。「$O(1)$」这个硬性要求是整道题的设计约束来源。调用次数可达 $2 \times 10^5$，任何 $O(n)$ 的实现（比如用数组维护顺序、每次淘汰时线性扫描找最旧的）都会超时。所以不能先想「怎么写对」，要先想「什么数据结构能同时做到 $O(1)$ 定位和 $O(1)$ 调整顺序」。
关键是要认清「使用」包含哪些动作。
get命中算一次使用；put更新一个已存在的 key 也算一次使用；put插入新 key 当然是最新的使用。这三处都必须把该 key 提升为「最新」，漏掉任何一处都会导致淘汰错误的 key。再看单一数据结构为什么不够。哈希表能 $O(1)$ 按 key 定位，但它无序，找不出谁最旧。链表能表达顺序（越靠前越新），但按 key 查找要 $O(n)$。于是自然的答案是组合：哈希表负责「从 key 找到位置」，链表负责「维护顺序并淘汰」。
最后一个推论决定了链表的类型：淘汰和「提升为最新」都需要把一个节点从链表中间摘下来。摘除一个节点要修改它前驱的
next，所以必须能 $O(1)$ 拿到前驱——单向链表做不到，必须是双向链表。
解法：哈希表 + 双向链表
核心思路
哈希表负责 $O(1)$ 定位节点，双向链表负责维护使用顺序：头部是最近使用，尾部是最久未使用。访问或更新节点后将其移到头部；容量超限时删除尾部节点。
节点同时保存
key和value，淘汰时才能根据尾节点的key同步删除哈希表记录。头尾哨兵用于统一插入、删除的边界处理。
解题步骤
- 用哈希表保存
key -> Node，创建头尾哨兵并相连。get：未命中返回-1；命中后把节点移到头部。put：已存在则更新值并移到头部；否则新建节点并插入头部。- 插入后若超出容量，删除尾部前的节点及其哈希表记录。
代码实现
class LRUCache {
private static class Node {
int key, value;
Node prev, next;
Node() {}
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<Integer, Node> cache = new HashMap<>();
private final Node head = new Node();
private final Node tail = new Node();
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
return;
}
node = new Node(key, value);
cache.put(key, node);
addToHead(node);
if (cache.size() > capacity) {
Node oldest = tail.prev;
remove(oldest);
cache.remove(oldest.key);
}
}
private void moveToHead(Node node) {
remove(node);
addToHead(node);
}
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
type Node struct {
key, value int
prev, next *Node
}
type LRUCache struct {
capacity int
cache map[int]*Node
head, tail *Node
}
func Constructor(capacity int) LRUCache {
head, tail := &Node{}, &Node{}
head.next, tail.prev = tail, head
return LRUCache{capacity: capacity, cache: map[int]*Node{}, head: head, tail: tail}
}
func (c *LRUCache) Get(key int) int {
node, ok := c.cache[key]
if !ok {
return -1
}
c.moveToHead(node)
return node.value
}
func (c *LRUCache) Put(key, value int) {
if node, ok := c.cache[key]; ok {
node.value = value
c.moveToHead(node)
return
}
node := &Node{key: key, value: value}
c.cache[key] = node
c.addToHead(node)
if len(c.cache) > c.capacity {
oldest := c.tail.prev
c.remove(oldest)
delete(c.cache, oldest.key)
}
}
func (c *LRUCache) moveToHead(node *Node) {
c.remove(node)
c.addToHead(node)
}
func (c *LRUCache) addToHead(node *Node) {
node.prev, node.next = c.head, c.head.next
c.head.next.prev, c.head.next = node, node
}
func (c *LRUCache) remove(node *Node) {
node.prev.next, node.next.prev = node.next, node.prev
}
复杂度分析
- 时间复杂度：
get、put均为平均 $O(1)$。- 空间复杂度：$O(capacity)$。
关键点总结
- 哈希表存节点引用，链表维护新旧顺序。
get命中、put更新和新增都要把节点设为最近使用。- 淘汰链表尾节点时，必须同步删除哈希表记录。
易错点总结
- 节点未保存
key，淘汰时无法清理哈希表。- 更新已有 key 时新建节点，导致链表出现重复节点。
- 只改链表或只改哈希表，破坏两者的一致性。
- 哨兵未正确相连，第一次插入就会访问空指针。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 460. LFU 缓存 | 困难 | 淘汰依据从「最久未用」换成「使用次数最少」，需按频次分桶再套 LRU |
| LCR 031. LRU 缓存 | 中等 | 与本题同题，可直接套用 |
| 面试题 16.25. LRU 缓存 | 中等 | 与本题同题，可直接套用 |
| 432. 全 O(1) 的数据结构 | 困难 | 同样是哈希加双向链表，但链表节点变成「同计数值的 key 集合」 |
| 155. 最小栈 | 简单 | 入门级的 $O(1)$ 数据结构设计，体会「用额外结构换查询复杂度」 |
| 706. 设计哈希映射 | 简单 | 反过来手写哈希表本身，理解本题所依赖的 $O(1)$ 查找从何而来 |
| 1206. 设计跳表 | 困难 | 另一种「多层链表换查询效率」的设计题，与本题互为参照 |