LeetCode LCR 031. LRU 缓存

2026-03-28 HGNULB 约 8 分钟

文章信息 5 个分类 5 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 031. LRU 缓存

题意分析

缓存有固定的正容量。get(key) 返回已有值，未命中返回 -1；put(key, value) 更新或新增键值，新增导致超出容量时，淘汰最久没有使用的键。

get 命中、put 覆盖和新增都算使用，需要更新该键的新旧顺序；未命中的查询不改变顺序。要满足进阶的常数时间要求，既要按键快速定位，也要快速调整任意节点的位置。

解法：哈希表与双向链表

核心思路

[!blue]

用哈希表 cache 保存“键 → 节点”，用双向链表按最近使用顺序连接这些节点：靠近头部的最新，靠近尾部的最旧。哈希定位节点后，可以直接通过它的前驱、后继将它摘下，不需要从头寻找位置。

每次使用已有键，就先从原位置摘除节点，再插到链表最前面。其他节点之间的相对顺序保持不变，因此链表仍按使用先后排列。需要淘汰时，最后一个真实节点就是最久未使用者，直接从两种结构中删除它。

节点同时保存 key 与 val：查询按节点取值，淘汰则用尾节点的 key 删除哈希记录。哈希表与链表始终表示同一批真实节点，更新值只修改原节点，不创建重复键节点。

链表两端放置 head、tail 哨兵，空链表时两者互相连接。这样每个真实节点都有前驱和后继，摘除、插头无需针对空表或单节点另写分支；真实首节点是 head.next，真实尾节点是 tail.prev。

Java 版先新增，再在 size > capacity 时删除尾部；Go 版在新增前检查是否已满，先删除旧尾部再插入。两种次序在方法返回时保持同一容量和使用顺序，覆盖已有键都不需要淘汰。

解题步骤

初始化空哈希表和头尾哨兵，Java 的真实节点计数从 0 开始，Go 直接使用哈希表大小。

get 未命中时返回 -1；命中时将节点移到最前面，再返回节点值。

put 命中时只更新原节点的值并移到最前面，不改变元素数量。

put 新增时，把新节点同时加入哈希表和链表头部；按实现选择在新增前或新增后淘汰旧尾节点，使容量不超限。

摘除时把前驱和后继双向接起来；插头时先保存原首节点并连接新节点，再修复头部和原首节点的两个方向。

淘汰时取 tail.prev，从链表摘除后，按它保存的键删除哈希记录。

代码实现

class Node {
    int key;
    int val;
    Node prev;
    Node next;

    Node() {}

    Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

class LRUCache {
    private Map<Integer, Node> cache = new HashMap<>();
    // 头尾哨兵：任何真实节点都有前驱后继，摘除与插入无需判空。
    private Node head = new Node();
    private Node tail = new Node();
    private int capacity;
    private int size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }

        Node node = cache.get(key);

        // 命中也算一次使用，必须提升。
        moveToHead(node);

        return node.val;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            // 覆盖不是插入：不新增节点，也不改 size。
            Node node = cache.get(key);

            node.val = value;
            moveToHead(node);
        } else {
            Node node = new Node(key, value);

            cache.put(key, node);
            addToHead(node);
            ++size;

            if (size > capacity) {
                // 节点里存了 key，才能反查哈希表把它一并删掉。
                node = removeTail();
                cache.remove(node.key);
                --size;
            }
        }
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next = node;
        node.next.prev = node;
    }

    private Node removeTail() {
        Node node = tail.prev;

        removeNode(node);

        return node;
    }
}

type node struct {
    key, val   int
    prev, next *node
}

type LRUCache struct {
    capacity   int
    cache      map[int]*node
    head, tail *node
}

func Constructor(capacity int) LRUCache {
    // 头尾哨兵：任何真实节点都有前驱后继，摘除与插入无需判空。
    head := new(node)
    tail := new(node)
    head.next = tail
    tail.prev = head
    return LRUCache{
        capacity: capacity,
        cache:    make(map[int]*node, capacity),
        head:     head,
        tail:     tail,
    }
}

func (this *LRUCache) Get(key int) int {
    n, ok := this.cache[key]
    if !ok {
        return -1
    }
    // 命中也算一次使用，必须提升。
    this.moveToFront(n)
    return n.val
}

func (this *LRUCache) Put(key int, value int) {
    n, ok := this.cache[key]
    if ok {
        // 覆盖不是插入：不新增节点。
        n.val = value
        this.moveToFront(n)
        return
    }
    if len(this.cache) == this.capacity {
        // 节点里存了 key，才能反查哈希表把它一并删掉。
        back := this.tail.prev
        this.remove(back)
        delete(this.cache, back.key)
    }
    n = &node{key: key, val: value}
    this.pushFront(n)
    this.cache[key] = n
}

func (this *LRUCache) moveToFront(n *node) {
    this.remove(n)
    this.pushFront(n)
}

func (this *LRUCache) remove(n *node) {
    n.prev.next = n.next
    n.next.prev = n.prev
    n.prev = nil
    n.next = nil
}

func (this *LRUCache) pushFront(n *node) {
    n.prev = this.head
    n.next = this.head.next
    this.head.next.prev = n
    this.head.next = n
}

复杂度分析

时间复杂度：get 与 put 均为平均 $O(1)$，哈希定位后只做固定数量的指针操作，淘汰也无需遍历。

空间复杂度：$O(capacity)$，保存缓存节点、键到节点的映射以及两个哨兵。

关键点总结

[!green]

哈希表负责定位，双向链表负责新旧顺序；移动节点后两者仍指向同一个对象。

使用过的节点移到最前面，未使用节点的相对顺序不变，因此尾部始终可以直接淘汰。

覆盖已有键只更新值和顺序，新增键才可能触发容量调整。

哨兵统一了边界指针操作，但不能作为真实缓存节点参与淘汰。

易错点总结

[!yellow]

get 命中和 put 覆盖都需要提升节点，只在新增时调整顺序会违反 LRU 语义。

淘汰必须同时删除链表节点和哈希记录，不能只改其中一份结构。

插头前要保留原首节点，摘除与插入都要维护前后两个方向。

覆盖原键不能增加 size 或创建新节点；Java 的计数只随真实增删变化。

容量由题目保证为正，尾部淘汰针对 tail.prev，不是哨兵 tail。

相似题目

题目	难度	关联与区别
460. LFU 缓存	困难	同样需要常数时间定位与更新淘汰顺序，LFU按频率分组，LRU只按最近使用顺序。
432. 全 O(1) 的数据结构	困难	同样结合哈希定位与双向链表维护动态顺序，原题维护频次桶，本题维护访问顺序。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/87325272

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！