基于栈实现LRUCache超时，如何优化代码效率？

问题描述 #

我正在解决LeetCode 146题LRU缓存：

设计符合LRU（Least Recently Used）缓存约束的数据结构。实现LRUCache类：

• LRUCache(int capacity)：以正整数容量capacity初始化LRU缓存。
• int get(int key)：若key存在则返回对应值，否则返回-1。
• void put(int key, int value)：若key存在则更新值；否则添加键值对，若超过容量则淘汰最近最少使用的键。

get和put操作均需达到平均O(1)时间复杂度。

以下是我的Java代码：

class LRUCache {
    Stack<Integer> stack;
    HashMap<Integer, Integer> cache;
    int capacity;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        stack = new Stack<>();
        cache = new HashMap<>();        
    }
    
    public int get(int key) {
        if(!cache.containsKey(key)) return -1;
        else 
            stack.removeElement(key);
            stack.push(key);
            return cache.get(key);
    }
    
    public void put(int key, int value) {
        if(cache.containsKey(key)){
            stack.removeElement(key);
        }
        else if(stack.size() == capacity){
            int leastRecent = stack.remove(0);
            cache.remove(leastRecent);
        }
        stack.push(key);
        cache.put(key, value);
    }
}

/*
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

所有测试用例均已通过，但出现“time limit exceeded”（超时）错误，请问如何优化代码效率？

优化方案 #

超时原因 #

你的代码超时核心问题是**Stack的核心操作无法达到O(1)时间复杂度**：

• removeElement(key)需要遍历整个栈查找目标元素，最坏情况为O(n)；
• remove(0)删除栈底元素时，后续所有元素都要向前移位，同样是O(n)操作。
  这直接导致get和put操作的时间复杂度退化为O(n)，在大规模数据测试下必然超时。

优化思路 #

要实现平均O(1)的get和put，必须结合两种数据结构：

• 哈希表：快速映射key到对应的节点，实现O(1)查找；
• 双向链表：快速完成节点的添加、删除、移动操作，所有链表操作均为O(1)。

优化后的Java代码 #

class LRUCache {
    // 定义双向链表节点
    class Node {
        int key;
        int value;
        Node prev;
        Node next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private HashMap<Integer, Node> cache;
    private Node head;
    private Node tail;
    private int capacity;
    private int size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        cache = new HashMap<>();
        // 虚拟头尾节点，简化边界处理
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        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);
        size++;
        // 超过容量时，删除链表尾部的最近最少使用节点
        if (size > capacity) {
            Node removedNode = removeTail();
            cache.remove(removedNode.key);
            size--;
        }
    }

    // 将节点添加到链表头部
    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 void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    // 删除链表尾部节点（最近最少使用的节点）
    private Node removeTail() {
        Node node = tail.prev;
        removeNode(node);
        return node;
    }
}

代码说明 #

1. 虚拟头尾节点：避免处理链表为空或单节点的边界情况，简化代码逻辑；
2. 哈希表映射：直接通过key获取链表节点，保证O(1)的查找效率；
3. 双向链表操作：所有链表相关操作（添加、删除、移动）均为O(1)时间复杂度，确保get和put操作的平均时间复杂度为O(1)；
4. size变量：实时记录缓存节点数量，避免遍历链表统计长度的额外开销。

内容的提问来源于stack exchange，提问作者Chinmaya Sahu