LeetCode 146. LRU 缓存

Categories:

Tags:

题目描述
思路分析
1. 解法一：哈希表 + 双向链表（推荐）
相似题目

题目描述

✅ 146. LRU 缓存

题目：

设计并实现一个满足 LRU（最近最少使用）缓存约束的数据结构，实现 LRUCache 类：

LRUCache(int capacity)：以正整数作为容量初始化缓存
int get(int key)：若键存在则返回其值，否则返回 -1
void put(int key, int value)：若键已存在则更新值；否则插入键值对。若插入后键数量超过容量，则逐出最久未使用的键

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

示例 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
lRUCache.put(3, 3); // 淘汰键 2，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1（未找到）
lRUCache.put(4, 4); // 淘汰键 1，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1（未找到）
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10^4
0 <= value <= 10^5
最多调用 2 * 10^5 次 get 和 put

思路分析

解法一：哈希表 + 双向链表（推荐）

核心思路：

用哈希表实现 key -> 节点 的 O(1) 定位。

用双向链表维护访问顺序，链表头表示最近使用，尾部表示最久未用。

get 命中后将节点移到头部；put 插入新节点到头部，超过容量时删除尾部。

复杂度分析：

时间复杂度：O(1)，其中每次 get/put 只涉及常数次链表和哈希表操作。

空间复杂度：O(capacity)，其中 capacity 表示缓存容量。

class LRUCache {
    private static class Node {
        int key;
        int value;
        Node prev;
        Node next;

        Node() {
        }

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

    private final int capacity;
    private final Map<Integer, Node> cache;
    private final Node head;
    private final Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 命中后移动到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node != null) {
            // 已存在则更新并移动到头部
            node.value = value;
            moveToHead(node);
            return;
        }

        Node newNode = new Node(key, value);
        cache.put(key, newNode);
        // 新节点插到头部
        addToHead(newNode);

        if (cache.size() > capacity) {
            // 超容量淘汰尾部节点
            Node removed = removeTail();
            cache.remove(removed.key);
        }
    }

    // 将节点移到头部
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    // 在链表头部插入节点
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    // 从链表中移除节点
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 移除尾部节点（最久未用）
    private Node removeTail() {
        Node last = tail.prev;
        removeNode(last);
        return last;
    }
}

type Node struct {
	key   int
	value int
	prev  *Node
	next  *Node
}

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

func Constructor(capacity int) LRUCache {
	head := &Node{}
	tail := &Node{}
	head.next = tail
	tail.prev = head

	return LRUCache{
		capacity: capacity,
		cache:    make(map[int]*Node),
		head:     head,
		tail:     tail,
	}
}

func (c *LRUCache) Get(key int) int {
	node, ok := c.cache[key]
	if !ok {
		return -1
	}
	// 命中后移动到头部
	c.moveToHead(node)
	return node.value
}

func (c *LRUCache) Put(key int, value int) {
	if node, ok := c.cache[key]; ok {
		// 已存在则更新并移动到头部
		node.value = value
		c.moveToHead(node)
		return
	}

	node := &Node{key: key, value: value}
	c.cache[key] = node
	// 新节点插到头部
	c.addToHead(node)

	if len(c.cache) > c.capacity {
		// 超容量淘汰尾部节点
		removed := c.removeTail()
		delete(c.cache, removed.key)
	}
}

// 将节点移到头部
func (c *LRUCache) moveToHead(node *Node) {
	c.removeNode(node)
	c.addToHead(node)
}

// 在链表头部插入节点
func (c *LRUCache) addToHead(node *Node) {
	node.prev = c.head
	node.next = c.head.next
	c.head.next.prev = node
	c.head.next = node
}

// 从链表中移除节点
func (c *LRUCache) removeNode(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

// 移除尾部节点（最久未用）
func (c *LRUCache) removeTail() *Node {
	last := c.tail.prev
	c.removeNode(last)
	return last
}

相似题目

题目	难度	考察点
460. LFU 缓存	困难	哈希表 + 双向链表
588. 设计内存文件系统	困难	树结构、哈希表设计
604. 迭代压缩字符串	简单	迭代器设计
1756. 设计最近使用过的列表	中等	队列 + MRU 设计
432. 全 O(1) 的数据结构	困难	哈希表 + 双向链表
1472. 设计浏览器历史记录	中等	双向链表设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/17639942