146. LRU 缓存 (Medium)

专题归类： 04-链表 · 07-栈与堆 LeetCode 链接： https://leetcode.cn/problems/lru-cache/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

请你设计并实现一个满足 LRU（最近最少使用）缓存约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) —— 以正整数作为容量初始化 LRU 缓存
• int get(int key) —— 如果关键字 key 存在于缓存中，返回关键字的值，否则返回 -1
• void put(int key, int value) —— 如果 key 已经存在，修改其 value；如果不存在，插入该键值对。当缓存容量达到上限时，应淘汰最久未使用的键值对

要求： get 和 put 的时间复杂度都是 O(1)。

---

题目详细分析

• 数据范围： capacity 在 [1, 3000] 范围内，key 和 value 在 [0, 10^4] 范围内，最多调用 2*10^5 次 get 和 put
• 输入特征： 需要设计一个数据结构，支持 O(1) 的查找、插入和删除
• 核心约束： 所有操作都必须是 O(1)——这意味着必须用哈希表实现 O(1) 查找，用链表实现 O(1) 插入/删除
• 隐藏条件： 为什么用双向链表而不是单向？因为淘汰最久未使用的元素需要删除链表尾部节点，单向链表无法 O(1) 删除尾节点（需要知道前驱）
• 边界条件： capacity = 1、重复 put 同一个 key、get 不存在的 key、put 时触发淘汰

---

小白版直白理解

就像你有一个只能放 3 本书的书架，每次你拿一本书看，就把它放到最顺手的位置（最左边）。当书架满了你又想加一本新书时，需要把最久没看的那本（最右边）丢掉。

具体操作：

• get(某书) → 找到书，看完了放回最左边
• put(新书) → 如果书架上已经有这本书，更新内容并移到最左边；如果没有，放在最左边，如果书架满了，丢掉最右边那本

这需要一个「快速查找」的目录（哈希表）和一个能「快速移动和删除」的书架（双向链表）。

---

解题思路

思路一：哈希表 + 双向链表（推荐）

为什么这样想： 我们需要同时满足 O(1) 查找和 O(1) 插入/删除。哈希表提供 O(1) 查找（key → 节点），双向链表提供 O(1) 的节点移动和删除。两者结合正好互补。

关键洞察： 双向链表维护使用顺序。最近使用的节点在头部，最久未使用的在尾部。每次访问（get/put）一个节点，就把它移动到头部。当容量满时，删除尾部节点。

为什么要用「虚拟头尾节点」？避免处理空链表和边界条件时的 None 检查，大大简化代码。

class DLinkedNode:
    """双向链表节点"""
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None
 
 
class LRUCache:
    """哈希表 + 双向链表实现 LRU 缓存"""
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key → node
        # 虚拟头尾节点
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._move_to_head(node)  # 移到头部表示最近使用
        return node.val
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # 更新值并移到头部
            node = self.cache[key]
            node.val = value
            self._move_to_head(node)
        else:
            # 创建新节点
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self._add_to_head(node)
            # 超出容量则淘汰尾部
            if len(self.cache) > self.capacity:
                removed = self._remove_tail()
                del self.cache[removed.key]
    
    def _add_to_head(self, node):
        """将节点插入到头部（head 之后）"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node):
        """删除节点"""
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _move_to_head(self, node):
        """将节点移到头部"""
        self._remove_node(node)
        self._add_to_head(node)
    
    def _remove_tail(self):
        """删除尾部节点，返回被删除的节点"""
        node = self.tail.prev
        self._remove_node(node)
        return node

思路二：使用 OrderedDict（Python 特性）

思路讲解： Python 的 collections.OrderedDict 底层也是哈希表 + 双向链表，可以直接利用。popitem(last=False) 可以移除最早插入的键值对（即最久未使用的）。这个方法利用了语言特性，面试时可能不被允许。

from collections import OrderedDict
 
class LRUCache:
    """基于 OrderedDict 实现"""
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()
    
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # 移到末尾（最近使用）
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # 移除最早插入的（最久未使用）
            self.cache.popitem(last=False)

---

易错点

• 双向链表指针修改顺序： 修改 4 个指针的顺序不能错。先连接新节点和 head.next，再连接 head 和新节点。建议画图确认
• head 和 tail 是虚拟节点： 不是实际数据节点，所以 cache 中存的 key 不会等于 head 或 tail
• 淘汰时哈希表和链表都要删： 删除尾部节点后，一定要执行 del self.cache[removed.key]，否则哈希表泄露
• put 更新已有 key 时： 先更新 node.val 再移到头部，否则移到头部后 node 的引用还在
• get 不存在的 key： 返回 -1 而不是 None，注意题目要求
• capacity = 1： 每次 put 都会触发淘汰，head.next 和 tail.prev 指向同一个节点

---

框架提炼

LRU 缓存设计模板： 哈希表 + 双向链表。

class DLinkedNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None
 
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_to_head(node)
    
    def _remove_tail(self):
        node = self.tail.prev
        self._remove_node(node)
        return node

设计思路总结： 需要 O(1) 操作时，思考哈希表（查找）+ 链表（顺序维护）的组合。这是数据结构设计中「以空间换时间」的经典案例。

---

关联题目

• 138-随机链表的复制 — 同样是哈希表 + 链表的数据结构操作
• 460-LFU缓存 — 更复杂的缓存淘汰策略（最少使用频率），是本题的进阶
• 剑指OfferII031-最近最少使用缓存 — 相同题目