好的，我们这次来详细讲解 LeetCode 第 146 题：LRU 缓存。

1. 题目描述

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

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以平均 O(1) 时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1，此时缓存是 {2=2, 1=1}（1 被访问，放到最近使用位置）
lRUCache.put(3, 3); // 逐出 key 2（最久未使用），缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 逐出 key 1，缓存是 {3=3, 4=4}
lRUCache.get(1);    // 返回 -1
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

2. 题目理解与需求分析

LRU 缓存淘汰策略：
当缓存空间不够时，淘汰 最久没有被访问 的数据。

O(1) 时间复杂度要求 意味着：

• get(key) 需要快速通过 key 找到对应的 value → 用 哈希表（字典）。
• 要维护数据的访问顺序（最近使用的在一边，最久未使用的在另一边）：
  • 在 get 和 put 时，如果 key 已存在，需要将其移到“最近使用”的位置（O(1) 时间内）。
  • 如果缓存满了，需要快速删除最久未使用的条目（O(1) 时间内）。

难点：
单纯哈希表无法记录顺序；单纯数组或链表删除、移动节点不是 O(1)。
→ 结合 哈希表 + 双向链表。

3. 数据结构设计

3.1 双向链表节点

每个节点存储：

• key
• value
• 前驱指针 prev
• 后继指针 next

3.2 整体结构

• 一个哈希表 cache：key → 对应的链表节点（实现 O(1) 查找）。
• 一个双向链表：
  • 越靠近头部表示越最近使用。
  • 越靠近尾部表示越最久未使用。
• 维护 size 和 capacity。

为了简化边界处理，使用虚拟头节点 (dummy head) 和虚拟尾节点 (dummy tail)：

head (最近使用) <-> node1 <-> node2 <-> ... <-> tail (最久未使用)

初始时 head.next = tail, tail.prev = head。

4. 需要实现的操作

4.1 辅助方法

(1) 将某个节点移到链表头部（表示最近使用）

def move_to_head(node):
    # 1. 先从原位置删除 node
    remove_node(node)
    # 2. 将 node 插入到 head 后面
    add_to_head(node)

(2) 从链表删除节点

def remove_node(node):
    node.prev.next = node.next
    node.next.prev = node.prev

(3) 在头部添加节点（最近使用）

def add_to_head(node):
    node.next = head.next
    node.prev = head
    head.next.prev = node
    head.next = node

(4) 删除尾部节点（最久未使用）

def remove_tail():
    last = tail.prev  # 最久未使用的节点
    remove_node(last)
    return last  # 返回该节点以便从哈希表删除

5. 主方法实现

5.1 get(key)

1. 在哈希表中查找 key：
   • 不存在 → 返回 -1。
   • 存在 → 获取对应节点，将其 move_to_head（因为被访问了），返回节点的 value。

5.2 put(key, value)

1. 在哈希表中查找 key：
   • 如果已存在：
     • 更新节点的 value。
     • 调用 move_to_head。
   • 如果不存在：
     • 创建新节点 (key, value)。
     • 将节点加入链表头部 add_to_head。
     • 在哈希表中添加映射。
     • 如果 size > capacity：
       • 调用 remove_tail 得到被删节点。
       • 在哈希表中删除该节点的 key。
       • size -= 1

6. 完整代码示例（Python）

class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = {}  # key -> node
        self.capacity = capacity
        self.size = 0
        # 虚拟头尾节点
        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.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.move_to_head(node)
        else:
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self.add_to_head(node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.remove_tail()
                del self.cache[removed.key]
                self.size -= 1

    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

7. 复杂度分析

• 时间复杂度：get 和 put 都是 O(1)（哈希表操作 O(1)，链表操作 O(1)）。
• 空间复杂度：O(capacity)，哈希表和双向链表最多存储 capacity 个元素。

8. 关键点总结

1. LRU 策略：最近使用的放头部，最久未使用的在尾部，满了就删尾部。
2. O(1) 实现：哈希表保证 O(1) 查找，双向链表保证 O(1) 增删节点。
3. 虚拟头尾节点：简化链表操作，避免空指针判断。
4. 访问（get）和更新（put 已存在） 都要把节点移到头部。
5. 插入新键（put 不存在） 时，如果超容量，要删除尾部节点并在哈希表里也删除。

这样，一个完整的 LRU 缓存就实现了。