146. LRU 缓存

LeetCode 原题链接

题目描述

实现固定容量的 LRU（最近最少使用）缓存：

  • get(key)：存在时返回值并标记为最近使用，否则返回 -1。
  • put(key, value)：写入或更新；超出容量时淘汰最久未使用项。
  • 两个操作都要求平均 O(1)。

题型判断

JavaScript 的 Map 不仅可以平均 O(1) 查找数据，还会按照插入顺序保存键。利用这个特性，可以让 Map 中的顺序表示数据的使用顺序：

  • 第一个 key 表示最久未使用的数据。
  • 最后一个 key 表示最近使用的数据。
  • 访问一个 key 时，先删除再重新插入，即可把它移动到最后。

核心思路

最久未使用 → ... → 最近使用
   Map 首部             Map 尾部
  • 命中 get：保存值，删除该 key 后重新插入，将它标记为最近使用。
  • 更新 put：先删除旧 key，再用新值重新插入。
  • 新增 put：直接插入 Map 尾部。
  • 超出容量：通过 this.cache.keys().next().value 取得并删除第一个 key。

代码实现

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

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

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

  this.cache.delete(key);
  this.cache.set(key, value);

  return value;
};

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

  this.cache.set(key, value);

  if (this.cache.size > this.capacity) {
    const leastRecentlyUsedKey = this.cache.keys().next().value;
    this.cache.delete(leastRecentlyUsedKey);
  }
};

复杂度与易错点

  • get、put：平均 O(1)。
  • 空间复杂度：O(capacity)。
  • 判断 key 是否存在必须使用 this.cache.has(key)，不能使用 if (!this.cache.get(key))，否则值为 0 时会被误判为不存在。
  • 更新已有 key 时必须写入本次传入的 value，不能重新写入旧值。
  • 无论新增还是更新，都要在写入后统一判断容量，避免新增 key 后提前返回而漏掉淘汰。
  • 仅调用 set 更新已有 key 的值不会改变它原来的顺序，因此必须先 delete 再 set。
  • 该解法依赖 JavaScript Map 保持插入顺序的语言特性；在不具备有序哈希表的语言中，通常需要使用“哈希表 + 双向链表”实现严格的 O(1) 操作。