LeetCode 146. LRU 缓存

Skyme2026/7/25大约 9 分钟

LeetCode 146. LRU 缓存

题目核心

请你设计并实现一个满足 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) 的平均时间复杂度运行。

LRU 是什么

LRU（Least Recently Used，最近最少使用）是一种缓存淘汰策略：

当缓存容量满了之后，优先删除那些最久没有被访问过的数据。
每次访问（get 或 put）某个数据后，这个数据就变成了"最近使用"的。

举个例子，假设缓存容量为 2：

put(1, 1)  → 缓存: {1=1}
put(2, 2)  → 缓存: {1=1, 2=2}      （最近使用：2）
get(1)     → 返回 1，缓存: {2=2, 1=1}  （最近使用：1）
put(3, 3)  → 缓存满了，删除最久未使用的 2
           → 缓存: {1=1, 3=3}      （最近使用：3）
get(2)     → 返回 -1（已被删除）

解法一：哈希表 + 双向链表（经典实现）

这是 LRU 缓存最经典的实现方式，使用哈希表保证查找 O(1)，使用双向链表维护使用顺序。

/**
 * 双向链表节点
 */
var Node = function (key = 0, value = 0) {
  this.key = key;
  this.value = value;

  this.prev = null;
  this.next = null;
};

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.size = 0;

  // 哈希表：key -> Node
  this.cache = new Map();

  // 两个虚拟节点
  this.head = new Node();
  this.tail = new Node();

  this.head.next = this.tail;
  this.tail.prev = this.head;
};

/**
 * 从双向链表中删除节点
 *
 * @param {Node} node
 */
LRUCache.prototype.removeNode = function (node) {
  node.prev.next = node.next;
  node.next.prev = node.prev;
};

/**
 * 把节点添加到链表尾部
 * tail 前面表示最近使用
 *
 * @param {Node} node
 */
LRUCache.prototype.addToTail = function (node) {
  node.prev = this.tail.prev;
  node.next = this.tail;

  this.tail.prev.next = node;
  this.tail.prev = node;
};

/**
 * 将某个节点移动到链表尾部
 *
 * @param {Node} node
 */
LRUCache.prototype.moveToTail = function (node) {
  this.removeNode(node);
  this.addToTail(node);
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (!this.cache.has(key)) {
    return -1;
  }

  const node = this.cache.get(key);

  // 被访问后变成最近使用
  this.moveToTail(node);

  return node.value;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  // key 已经存在
  if (this.cache.has(key)) {
    const node = this.cache.get(key);

    // 更新值
    node.value = value;

    // 更新为最近使用
    this.moveToTail(node);

    return;
  }

  // 创建新节点
  const newNode = new Node(key, value);

  // 加入哈希表
  this.cache.set(key, newNode);

  // 加到链表尾部，表示最近使用
  this.addToTail(newNode);

  this.size++;

  // 超出容量，删除最久未使用节点
  if (this.size > this.capacity) {
    const oldestNode = this.head.next;

    this.removeNode(oldestNode);
    this.cache.delete(oldestNode.key);

    this.size--;
  }
};

经典实现代码逐行解释

Node 构造函数

var Node = function (key = 0, value = 0) {
  this.key = key;
  this.value = value;

  this.prev = null;
  this.next = null;
};

双向链表的节点结构：

key：存储键，删除节点时需要通过 key 去哈希表里删除对应记录。
value：存储值。
prev：前驱指针。
next：后继指针。

LRUCache 构造函数

var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.size = 0;

  this.cache = new Map();

  this.head = new Node();
  this.tail = new Node();

  this.head.next = this.tail;
  this.tail.prev = this.head;
};

capacity：缓存的最大容量。
size：当前缓存中的元素数量。
cache：哈希表，key 对应到链表中的节点，实现 O(1) 查找。
head 和 tail：两个虚拟节点（哨兵节点），分别表示链表的头和尾。
- head.next 指向最久未使用的节点。
- tail.prev 指向最近使用的节点。

为什么要用虚拟节点？

虚拟节点可以简化边界情况的处理，不需要在插入或删除时判断节点是否在头部或尾部。

removeNode 方法

LRUCache.prototype.removeNode = function (node) {
  node.prev.next = node.next;
  node.next.prev = node.prev;
};

从双向链表中删除一个节点：

让前驱节点的 next 指向后继节点。
让后继节点的 prev 直接指向前驱节点。

这样 node 就从链表中"脱链"了。

addToTail 方法

LRUCache.prototype.addToTail = function (node) {
  node.prev = this.tail.prev;
  node.next = this.tail;

  this.tail.prev.next = node;
  this.tail.prev = node;
};

把节点添加到链表尾部（tail 之前），表示最近使用。

一共要修改 4 个指针：

node.prev 指向原来的最后一个节点（tail.prev）。
node.next 指向 tail。
原来最后一个节点的 next 指向 node。
tail.prev 指向 node。

moveToTail 方法

LRUCache.prototype.moveToTail = function (node) {
  this.removeNode(node);
  this.addToTail(node);
};

把节点移动到尾部，标记为最近使用：

先从当前位置删除。
再添加到尾部。

get 方法

LRUCache.prototype.get = function (key) {
  if (!this.cache.has(key)) {
    return -1;
  }

  const node = this.cache.get(key);

  this.moveToTail(node);

  return node.value;
};

获取缓存值：

如果 key 不存在，返回 -1。
如果存在，通过哈希表 O(1) 找到节点。
把这个节点移动到链表尾部（标记为最近使用）。
返回节点的值。

put 方法

LRUCache.prototype.put = function (key, value) {
  if (this.cache.has(key)) {
    const node = this.cache.get(key);
    node.value = value;
    this.moveToTail(node);
    return;
  }

如果 key 已经存在：

更新节点的值。
把节点移动到尾部（标记为最近使用）。

  const newNode = new Node(key, value);
  this.cache.set(key, newNode);
  this.addToTail(newNode);
  this.size++;

如果 key 不存在：

创建新节点。
存入哈希表。
添加到链表尾部。
大小加一。

  if (this.size > this.capacity) {
    const oldestNode = this.head.next;

    this.removeNode(oldestNode);
    this.cache.delete(oldestNode.key);

    this.size--;
  }
};

如果超出容量：

最久未使用的节点是 head.next（链表头部）。
从链表中删除。
从哈希表中删除（需要节点里存 key，就是为了这一步）。
大小减一。

经典实现的执行过程

以容量为 2 为例：

初始状态：
  head <-> tail
  cache = {}
  size = 0

put(1, 1):
  创建节点 Node(1, 1)
  cache = {1: Node(1,1)}
  head <-> Node(1,1) <-> tail
  size = 1

put(2, 2):
  创建节点 Node(2, 2)
  cache = {1: Node(1,1), 2: Node(2,2)}
  head <-> Node(1,1) <-> Node(2,2) <-> tail
  size = 2

get(1):
  找到 Node(1,1)
  移到尾部：head <-> Node(2,2) <-> Node(1,1) <-> tail
  返回 1

put(3, 3):
  key 不存在，创建 Node(3, 3)
  加到尾部：head <-> Node(2,2) <-> Node(1,1) <-> Node(3,3) <-> tail
  size = 3 > 2，需要淘汰
  淘汰 head.next = Node(2,2)
  cache 删除 key=2
  head <-> Node(1,1) <-> Node(3,3) <-> tail
  size = 2

get(2):
  cache 中没有 key=2，返回 -1

经典实现的优缺点

优点	缺点
get 和 put 都是 O(1)	代码相对较长，需要手动维护链表
思路清晰，面试常考	指针操作容易出错
不依赖语言特性，所有语言通用

解法二：利用 Map 特性（简洁写法）

JavaScript 的 Map 有一个特性：它会按照元素的插入顺序来维护键值对。利用这个特性，可以非常简洁地实现 LRU 缓存。

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.value = new Map();
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (!this.value.has(key)) {
    return -1;
  }
  const val = this.value.get(key);
  this.value.delete(key);
  this.value.set(key, val);
  return val;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  // 如果已经存在
  if (this.value.has(key)) {
    this.value.delete(key);
    this.value.set(key, value);
  } else {
    if (this.value.size == this.capacity) {
      // 达到容量
      const last = this.value.keys().next().value;
      this.value.delete(last);
    }
    this.value.set(key, value);
  }
};

Map 写法代码逐行解释

构造函数

var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.value = new Map();
};

capacity：缓存容量。
value：一个 Map，用来存储键值对。Map 会按照插入顺序维护元素。

get 方法

LRUCache.prototype.get = function (key) {
  if (!this.value.has(key)) {
    return -1;
  }
  const val = this.value.get(key);
  this.value.delete(key);
  this.value.set(key, val);
  return val;
};

获取缓存值的思路：

如果 key 不存在，返回 -1。
如果存在，先把值取出来。
关键：删除这个 key，再重新 set 进去。这样它就变成了"最新插入"的，也就是最近使用的。
返回值。

为什么删除再插入就可以表示"最近使用"？

因为 Map 的迭代顺序是插入顺序。把一个 key 删掉再重新插入，它就会跑到顺序的最后面，表示最近使用。

put 方法

LRUCache.prototype.put = function (key, value) {
  if (this.value.has(key)) {
    this.value.delete(key);
    this.value.set(key, value);
  }

如果 key 已经存在：

先删掉旧的。
再 set 新值（这样它就跑到最后面了）。

  } else {
    if (this.value.size == this.capacity) {
      const last = this.value.keys().next().value;
      this.value.delete(last);
    }
    this.value.set(key, value);
  }
};

如果 key 不存在：

如果缓存已满，需要淘汰最久未使用的。
- this.value.keys().next().value 获取 Map 中第一个 key（最久未使用的）。
- 删除这个 key。
把新的 key-value set 进去（自动排到最后）。

this.value.keys().next().value 是什么？

this.value.keys() 返回一个 Map 的迭代器，按插入顺序遍历所有 key。
.next() 调用迭代器的 next 方法，得到第一个元素。
.value 获取这个元素的值，也就是第一个 key。

第一个 key 就是最久未使用的，所以要删掉它。

Map 写法的执行过程

以容量为 2 为例：

初始状态：
  value = Map{}

put(1, 1):
  key 不存在，容量未满
  value = Map{1 => 1}

put(2, 2):
  key 不存在，容量未满
  value = Map{1 => 1, 2 => 2}

get(1):
  key 存在
  val = 1
  删除 key 1 → value = Map{2 => 2}
  重新 set(1, 1) → value = Map{2 => 2, 1 => 1}
  返回 1

put(3, 3):
  key 不存在
  size = 2 == capacity = 2，需要淘汰
  keys().next().value = 2（第一个 key）
  删除 key 2 → value = Map{1 => 1}
  set(3, 3) → value = Map{1 => 1, 3 => 3}

get(2):
  key 不存在，返回 -1

Map 写法的优缺点

优点	缺点
代码非常简洁	依赖 JavaScript Map 的特性，不是通用写法
容易理解和记忆	面试官可能希望你用链表实现，考察数据结构能力
实际开发中可以直接用	删了又插，性能理论上略低（虽然都是 O(1)）

两种解法对比

解法	时间复杂度	空间复杂度	特点
哈希表 + 双向链表	O(1)	O(n)	经典实现，面试首选，不依赖语言特性
Map 写法	O(1)	O(n)	代码简洁，依赖 JS 特性，适合快速解题

面试时怎么选

如果面试官明确要求手写数据结构：用哈希表 + 双向链表的经典实现。
如果只是快速解题（比如刷题平台）：Map 写法更简洁，不容易写错。
两种都掌握最好：经典实现考察的是你对数据结构的理解，Map 写法考察的是你对语言特性的熟悉程度。

使用示例

const 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}
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

为什么双向链表而不是单向链表

因为删除节点的时候，需要同时知道前驱节点和后继节点：

单向链表只能 O(1) 找到后继，找前驱需要从头遍历，是 O(n)。
双向链表每个节点都有 prev 指针，可以 O(1) 找到前驱。

所以要实现 O(1) 的删除操作，必须用双向链表。

为什么节点里要存 key

淘汰最久未使用节点时，我们从链表头部拿到节点，然后需要从哈希表里也删掉这个记录。

哈希表是通过 key 来删除的，所以节点里必须存 key，才能知道要删哈希表里的哪一项。

const oldestNode = this.head.next;
this.cache.delete(oldestNode.key);  // 需要用节点里的 key

如果节点里只存 value 不存 key，就没法从哈希表里删除对应记录了。