146. LRU Cache

📘 題目敘述

設計一個資料結構，符合「最近最少使用」（Least Recently Used, LRU）快取的限制。

請實作 LRUCache 類別：

LRUCache(int capacity)：用正整數 capacity 初始化 LRU 快取容量。
int get(int key)：如果 key 存在，回傳對應的值；否則回傳 -1。
void put(int key, int value)：如果 key 已存在，更新其值；否則加入新的 (key, value)。如果這次加入後 key 的數量超過容量，請移除「最近最少使用」的 key。

get 與 put 都必須在平均 O(1) 時間內完成。

條件限制

1 <= capacity <= 3000
0 <= key <= 10^4
0 <= value <= 10^5
get 和 put 的總呼叫次數最多為 2 * 10^5

🧠 解題思路

LRU 的核心就是兩件事要同時做到，而且都要快：

O(1) 查某個 key 是否存在、並取得 value
O(1) 把「最近使用」更新到最前面，並在超容量時 O(1) 刪掉最久沒用的那個

所以我用兩個結構搭配：

用 list<pair<int,int>> nums 存快取內容，並且維護「使用順序」
- list 的前面是「最新使用」
- list 的後面是「最久沒用」
用 unordered_map<int, list<pair<int,int>>::iterator> m 做 key 到 list 節點位置的映射
- 這樣 get(key) 能 O(1) 直接找到 list 的那個節點
- 找到後用 splice 把節點搬到最前面，代表「剛被使用」

所有變數

nums：list<pair<int,int>>，每個節點存 (key, value)，並用節點順序表示 LRU 次序（前新後舊）
m：unordered_map<int, list<pair<int,int>>::iterator>，把 key 對應到 nums 中那個 (key,value) 節點的位置
cap：快取容量上限
now：在 get / put 中用來接住 m[key] 的 iterator，指向 nums 裡的某個節點
val：在 get 中取出的對應 value
k：在 put 超容量時，抓 nums.back() 得到的最後一個節點 (key,value)
del：要被移除的 key（也就是最久沒用的那個 key）

🪜 主要流程步驟

1. 初始化：只記住容量 cap

建構子只做一件事：把 cap = capacity 存起來。 nums 和 m 預設都是空的，從第一次 put 開始才會逐步塞資料。

2. get(key)：O(1) 查詢 + 更新為「最新使用」

如果 m 裡沒有 key，代表不在快取中，回傳 -1。
如果存在：
- now = m[key] 會拿到 list 節點位置
- val = now->second 取出 value
- 用 nums.splice(nums.begin(), nums, now) 把該節點搬到最前面。這一步是 LRU 的關鍵：表示這個 key 剛剛被使用，現在是「最新」。
- 回傳 val

3. put(key, value)：分成「已存在」與「不存在」

先看 key 是否已在 m 裡。

4. put：如果 key 已存在 → 更新值 + 搬到最前面

now = m[key] 找到節點
now->second = value 更新 value
nums.splice(nums.begin(), nums, now) 搬到最前面，表示剛被使用
結束

5. put：如果 key 不存在 → 可能要先淘汰，再插入新節點

如果 nums.size() == cap，代表容量已滿：

k = nums.back() 取得最後面那個 (key,value)（最久沒用）
del = k.first 取出要刪掉的 key
m.erase(del) 把 map 裡的索引刪掉
nums.pop_back() 把 list 最後的節點刪掉

然後把新資料塞進去：

nums.push_front({key, value}) 新節點放最前面（最新使用）
m[key] = nums.begin() 把 key 對應到新節點位置

⏱️ 複雜度

時間複雜度：get 平均 O(1)，put 平均 O(1)
空間複雜度：O(capacity)（list 與 hash table 最多存 capacity 筆）

💻 程式碼實作

class LRUCache {
public:
    list<pair<int, int>> nums;
    unordered_map<int, list<pair<int, int>>::iterator> m;
    int cap;

    LRUCache(int capacity) {
        cap = capacity;
    }

    int get(int key) {
        if (!m.count(key)) {
            return -1;
        }
        auto now = m[key]; // 指向 list 中的 iterator
        int val = now->second;
        nums.splice(nums.begin(), nums, now); // 插入最前面
        return val;
    }

    void put(int key, int value) {
        if (m.count(key)) {
            auto now = m[key];
            now->second = value;
            nums.splice(nums.begin(), nums, now);
            return;
        }
        if (nums.size() == cap) {
            auto k = nums.back();
            int del = k.first;
            m.erase(del);
            nums.pop_back();
        }
        nums.push_front({key, value});
        m[key] = nums.begin();
    }
};

🔗 題目連結

https://leetcode.com/problems/lru-cache/