← All notes

Leetcode记录：缓存

Table of contents

• LRU 缓存
  • 为什么使用哈希表和双向链表
  • get() 为什么这样执行
  • put() 为什么分成三种情况
  • touch() 和 splice() 的作用
  • 复杂度和容易写错的地方
• LFU 缓存
  • LFU 比 LRU 多解决了什么
  • get() 为什么必须增加频率
  • put() 的执行顺序
  • increaseFrequency() 每一步的原因
  • 复杂度和不变量
• 基于时间的键值存储
  • 为什么使用哈希表加有序数组
  • set() 为什么可以直接追加
  • get() 为什么使用 upper_bound
  • 复杂度
• 设计一个验证系统
  • 为什么同时维护哈希表和时间队列
  • generate() 为什么写两个容器
  • renew() 为什么先清理过期令牌
  • removeExpired() 中为什么必须比较过期时间
  • countUnexpiredTokens() 为什么只返回哈希表大小
  • 复杂度
• 全 O(1) 的数据结构
  • 为什么普通哈希表不够
  • 新 key 的 inc() 为什么放入 count 1
  • 已有 key 的 inc() 为什么只检查下一个 bucket
  • dec() 为什么分 count 等于 1 和大于 1
  • 为什么最大值和最小值是 O(1)
  • 为什么必须删除空 bucket
  • 复杂度和关键不变量

LRU 缓存

Leetcode 146. 请设计并实现一个满足 LRU（最近最少使用）约束的数据结构。实现 LRUCache(int capacity)、int get(int key) 和 void put(int key, int value)，并使 get、put 的平均时间复杂度均为 $O(1)$。

为什么使用哈希表和双向链表

这道题同时要求完成两件事：

1. 根据 key 在 $O(1)$ 平均时间内找到缓存项；
2. 在 $O(1)$ 时间内更新访问顺序，并删除最久未使用的缓存项。

单独使用哈希表可以快速查找，但它不记录访问顺序；单独使用链表可以维护顺序，但根据 key 查找节点需要 $O(n)$。因此需要组合使用：

• list<pair<int, int>> cache_ 按照 MRU 到 LRU 保存 (key, value)，链表头是最近使用，链表尾是最久未使用；
• unordered_map<int, ListIterator> index_ 保存 key -> 链表节点迭代器，通过 key 可以直接定位节点；
• 双向链表已知节点位置后，可以在 $O(1)$ 时间内删除或移动节点。

始终维护下面两个不变量：

cache_.front()                         cache_.back()
最近使用 MRU  ->  ...  ->  ...  ->  最久未使用 LRU

index_[key] ---------------> key 对应的链表节点

class LRUCache {
public:
    explicit LRUCache(int capacity) : capacity_(capacity) {}

    int get(int key) {
        auto it = index_.find(key);
        if (it == index_.end()) {
            return -1;
        }
        touch(it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = index_.find(key);
        if (it != index_.end()) {
            it->second->second = value;
            touch(it->second);
            return;
        }

        if (static_cast<int>(cache_.size()) == capacity_) {
            index_.erase(cache_.back().first);
            cache_.pop_back();
        }

        cache_.emplace_front(key, value);
        index_[key] = cache_.begin();
    }

private:
    using ListIterator = std::list<std::pair<int, int>>::iterator;

    void touch(ListIterator it) {
        cache_.splice(cache_.begin(), cache_, it);
    }

    int capacity_;
    std::list<std::pair<int, int>> cache_;  // MRU -> LRU
    std::unordered_map<int, ListIterator> index_;
};

get() 为什么这样执行

auto it = index_.find(key);

先查哈希表，而不是遍历链表，这样平均时间复杂度为 $O(1)$。如果不存在，直接返回 -1；如果存在，it->second 就是对应链表节点的迭代器。

touch(it->second);
return it->second->second;

读取也算一次使用，所以返回值之前必须调用 touch() 将节点移动到链表头。链表节点保存的是 (key, value)，因此迭代器的 second 才是缓存值。

put() 为什么分成三种情况

第一种情况是 key 已经存在：

it->second->second = value;
touch(it->second);

既要更新 value，也要把它标记为最近使用。如果只修改 value 而不更新顺序，之后可能错误淘汰一个刚刚更新过的 key。

第二种情况是 key 不存在并且容量已满：

index_.erase(cache_.back().first);
cache_.pop_back();

链表尾就是最久未使用的节点。删除时必须先从哈希表移除 key，再删除链表节点，否则哈希表中会留下一个已经失效的迭代器。

第三种情况是插入新 key：

cache_.emplace_front(key, value);
index_[key] = cache_.begin();

新写入的数据刚刚被使用，所以直接放在链表头；随后将新节点的迭代器记录到哈希表。两个数据结构必须一起更新，否则它们的内容会不一致。

touch() 和 splice() 的作用

void touch(ListIterator it) {
    cache_.splice(cache_.begin(), cache_, it);
}

splice(position, source, it) 将 source 中 it 指向的节点移动到 position 前面。这里 source 和目标都是 cache_，所以它的含义是把已有节点移动到链表头。

splice() 不复制 (key, value)，也不重新分配节点，时间复杂度为 $O(1)$。更重要的是，被移动节点的迭代器不会失效，因此 index_[key] 仍然指向正确节点，不需要重新写入哈希表。

例如当前顺序为：

[3] -> [1] -> [5] -> [2]

访问 key 5 后调用 touch()：

[5] -> [3] -> [1] -> [2]

此时 5 成为 MRU，下一次容量满时首先淘汰尾部的 2。

复杂度和容易写错的地方

• get()：哈希查找和链表移动，平均 $O(1)$；
• put()：哈希查找、链表插入/删除/移动，平均 $O(1)$；
• 空间复杂度：哈希表和链表各保存至多 capacity 个节点，为 $O(capacity)$。

常见错误是只在 put() 时更新访问顺序，而忘记成功的 get() 同样代表一次使用；或者删除链表尾后没有同步删除哈希表记录。Leetcode 保证 capacity >= 1，如果用于通用代码，还应单独处理容量为 0 的情况。

LFU 缓存

Leetcode 460. 请设计并实现 LFU（最不经常使用）缓存。容量满时先淘汰访问频率最低的键；若多个键频率相同，则淘汰其中最久未使用的键。get 和 put 的平均时间复杂度均要求为 $O(1)$。

LFU 比 LRU 多解决了什么

LRU 只需要维护一条访问顺序；LFU 的淘汰规则有两层：

1. 先找访问频率最小的 key；
2. 如果频率相同，再淘汰该频率中最久未使用的 key。

因此不能只使用一条 LRU 链表。这里维护三个结构：

• entries_：key -> Entry，用于 $O(1)$ 找到 value、当前频率以及 key 在频率链表中的位置；
• frequencyKeys_：frequency -> list<key>，相同频率的 key 按 MRU 到 LRU 排列；
• minFrequency_：记录当前缓存中最小频率，避免淘汰时扫描所有频率。

frequencyKeys_[1]: [最近使用] -> ... -> [最久未使用]
frequencyKeys_[2]: [最近使用] -> ... -> [最久未使用]
frequencyKeys_[3]: [最近使用] -> ... -> [最久未使用]
                      ^
entries_[key].position 指向 key 所在的具体节点

每个 key 只会出现在一个频率链表中。Entry::position 的作用与 LRU 中的哈希表迭代器相同：让程序不必遍历链表就能删除指定 key。

class LFUCache {
public:
    explicit LFUCache(int capacity) : capacity_(capacity) {}

    int get(int key) {
        auto it = entries_.find(key);
        if (it == entries_.end()) {
            return -1;
        }
        increaseFrequency(key, it->second);
        return it->second.value;
    }

    void put(int key, int value) {
        if (capacity_ == 0) {
            return;
        }

        auto it = entries_.find(key);
        if (it != entries_.end()) {
            it->second.value = value;
            increaseFrequency(key, it->second);
            return;
        }

        if (static_cast<int>(entries_.size()) == capacity_) {
            auto &bucket = frequencyKeys_[minFrequency_];
            int evictedKey = bucket.back();
            bucket.pop_back();
            if (bucket.empty()) {
                frequencyKeys_.erase(minFrequency_);
            }
            entries_.erase(evictedKey);
        }

        minFrequency_ = 1;
        auto &bucket = frequencyKeys_[1];
        bucket.push_front(key);
        entries_.emplace(key, Entry{value, 1, bucket.begin()});
    }

private:
    struct Entry {
        int value;
        int frequency;
        std::list<int>::iterator position;
    };

    void increaseFrequency(int key, Entry &entry) {
        int oldFrequency = entry.frequency;
        auto bucketIt = frequencyKeys_.find(oldFrequency);
        bucketIt->second.erase(entry.position);

        if (bucketIt->second.empty()) {
            frequencyKeys_.erase(bucketIt);
            if (minFrequency_ == oldFrequency) {
                ++minFrequency_;
            }
        }

        ++entry.frequency;
        auto &newBucket = frequencyKeys_[entry.frequency];
        newBucket.push_front(key);
        entry.position = newBucket.begin();
    }

    int capacity_;
    int minFrequency_ = 0;
    std::unordered_map<int, Entry> entries_;
    std::unordered_map<int, std::list<int>> frequencyKeys_;
};

get() 为什么必须增加频率

auto it = entries_.find(key);

不存在时返回 -1。存在时，一次成功读取就意味着该 key 又被使用了一次，所以不能直接返回 value，而要先调用：

increaseFrequency(key, it->second);

这一步将 key 从频率 f 的链表移动到频率 f + 1 的链表头，然后返回 value。

put() 的执行顺序

容量为 0 时不能插入任何元素，因此首先返回：

if (capacity_ == 0) {
    return;
}

如果 key 已经存在，更新 value，并将这次更新视为一次访问：

it->second.value = value;
increaseFrequency(key, it->second);

如果 key 不存在且容量已满，需要先淘汰：

auto &bucket = frequencyKeys_[minFrequency_];
int evictedKey = bucket.back();

minFrequency_ 直接定位最低频率；该频率链表的尾部是同频率中最久未使用的 key，因此 bucket.back() 同时满足 LFU 和 LRU 两层淘汰规则。随后要从频率链表和 entries_ 中都删除它。

新 key 的初始频率一定是 1，而且它刚被写入，是频率 1 中最近使用的元素：

minFrequency_ = 1;
bucket.push_front(key);
entries_.emplace(key, Entry{value, 1, bucket.begin()});

插入新 key 后最小频率必然变成 1，所以可以直接设置 minFrequency_ = 1。

increaseFrequency() 每一步的原因

首先从旧频率链表删除 key：

int oldFrequency = entry.frequency;
auto bucketIt = frequencyKeys_.find(oldFrequency);
bucketIt->second.erase(entry.position);

使用保存的迭代器可以 $O(1)$ 删除准确节点。如果删除后旧频率链表为空，就不再保留空桶：

if (bucketIt->second.empty()) {
    frequencyKeys_.erase(bucketIt);
    if (minFrequency_ == oldFrequency) {
        ++minFrequency_;
    }
}

只有当空桶正好是最低频率时才更新 minFrequency_。这里可以直接加 1，是因为当前操作只把一个 key 从 oldFrequency 移到 oldFrequency + 1；如果旧的最小频率已经没有其他 key，下一个最小频率不可能越过 oldFrequency + 1。

最后增加 Entry 中的频率，把 key 放到新频率链表头，并更新迭代器：

++entry.frequency;
auto &newBucket = frequencyKeys_[entry.frequency];
newBucket.push_front(key);
entry.position = newBucket.begin();

必须更新 entry.position，因为原来的迭代器指向旧链表中已经删除的节点。

复杂度和不变量

• get()、put() 平均时间复杂度均为 $O(1)$；
• 每个 key 在 entries_ 中保存一次，并在某个频率链表中保存一次，空间复杂度为 $O(capacity)$；
• 每个频率链表始终按照 MRU 到 LRU 排列；
• minFrequency_ 始终指向当前至少包含一个 key 的最小频率。

常见错误包括：只维护频率而没有维护同频率内的 LRU 顺序；淘汰链表节点后忘记删除 entries_；移动 key 后忘记更新保存的迭代器；以及插入新 key 后忘记将 minFrequency_ 重置为 1。

基于时间的键值存储

Leetcode 981. 设计一个可以在不同时间保存同一键多个值的键值存储。set(key, value, timestamp) 保存数据；get(key, timestamp) 返回时间戳不超过给定值的最新记录，不存在时返回空字符串。

为什么使用哈希表加有序数组

不同 key 的历史互不相关，所以先用哈希表按 key 分组：

unordered_map<string, vector<pair<int, string>>> history_;

每个 vector 保存该 key 的 (timestamp, value) 历史。题目保证同一个 key 的 set() 时间戳严格递增，因此只要在尾部 emplace_back()，vector 就天然按照时间升序排列，不需要每次重新排序。

之所以使用 vector 而不是 map<timestamp, value>，是因为这里的写入只发生在尾部，而查询可以二分。vector 内存连续、额外开销小，并且二分查找的 cache locality 更好。

class TimeMap {
public:
    void set(std::string key, std::string value, int timestamp) {
        history_[std::move(key)].emplace_back(timestamp, std::move(value));
    }

    std::string get(std::string key, int timestamp) {
        auto mapIt = history_.find(key);
        if (mapIt == history_.end()) {
            return "";
        }

        const auto &records = mapIt->second;
        auto it = std::upper_bound(
            records.begin(), records.end(), timestamp,
            [](int target, const auto &record) {
                return target < record.first;
            });

        if (it == records.begin()) {
            return "";
        }
        return std::prev(it)->second;
    }

private:
    std::unordered_map<std::string,
                       std::vector<std::pair<int, std::string>>> history_;
};

set() 为什么可以直接追加

history_[std::move(key)].emplace_back(timestamp, std::move(value));

history_[key] 在 key 不存在时会创建一个空 vector，存在时返回已有历史。由于时间戳严格递增，新记录一定属于 vector 尾部，所以追加后仍然有序。

参数是按值传入的局部对象，写入容器后不再使用，因此用 std::move 将 string 的内部资源转交给容器，避免一次不必要的字符串复制。这是性能优化，不影响算法本身；写成普通复制也能得到正确结果。

get() 为什么使用 upper_bound

首先检查 key 是否存在：

auto mapIt = history_.find(key);
if (mapIt == history_.end()) {
    return "";
}

不能直接使用 history_[key] 查询，因为 operator[] 会在 key 不存在时插入一个空 vector，而查询操作不应该修改数据结构。

接下来要找的是“最后一个 record.timestamp <= timestamp”。代码先用 upper_bound 找到第一个严格大于目标时间的记录：

auto it = std::upper_bound(
    records.begin(), records.end(), timestamp,
    [](int target, const auto &record) {
        return target < record.first;
    });

这里比较的是一个整数目标时间和一个 (timestamp, value) 记录。返回的 it 满足：

it 之前的时间戳 <= target
it 及其之后的时间戳 > target

因此答案是 std::prev(it)。如果 it == records.begin()，说明连第一条记录的时间都大于目标时间，不存在可见历史，应返回空字符串。

例如记录时间为 [1, 4, 8]，查询时间为 6，upper_bound 指向 8，向前一步得到时间 4 的值。

复杂度

• set()：vector 尾部追加，摊还 $O(1)$；
• get()：先平均 $O(1)$ 查 key，再在该 key 的 $m$ 条历史中二分，复杂度为 $O(\log m)$；
• 空间复杂度：所有历史记录总数为 $O(n)$。

关键前提是同一个 key 的时间戳按递增顺序写入。如果实际业务允许乱序写入，就不能无条件追加，需要在有序位置插入、先收集后排序，或者改用有序映射。

设计一个验证系统

Leetcode 1797. 给定统一的存活时间 timeToLive，实现令牌的生成、续期和未过期令牌计数。令牌在 currentTime >= expirationTime 时视为过期，续期只能作用于当前仍有效的令牌。

为什么同时维护哈希表和时间队列

这里也有两个不同的查询目标：

• 根据 tokenId 判断令牌是否存在，并读取它当前最新的过期时间；
• 按照过期时间快速清理已经失效的令牌。

因此使用：

• expiration_：tokenId -> 最新 expirationTime，它是令牌当前状态的权威记录；
• timeline_：按照过期时间排列的 (expirationTime, tokenId) 队列，用于从最早到最晚批量清理。

题目保证调用中的 currentTime 严格递增，并且所有令牌使用相同的 timeToLive，所以每次生成或续期得到的新过期时间也递增，可以直接追加到队尾。

class AuthenticationManager {
public:
    explicit AuthenticationManager(int timeToLive)
        : timeToLive_(timeToLive) {}

    void generate(std::string tokenId, int currentTime) {
        int expirationTime = currentTime + timeToLive_;
        expiration_[tokenId] = expirationTime;
        timeline_.emplace_back(expirationTime, std::move(tokenId));
    }

    void renew(std::string tokenId, int currentTime) {
        removeExpired(currentTime);
        auto it = expiration_.find(tokenId);
        if (it == expiration_.end()) {
            return;
        }

        int expirationTime = currentTime + timeToLive_;
        it->second = expirationTime;
        timeline_.emplace_back(expirationTime, std::move(tokenId));
    }

    int countUnexpiredTokens(int currentTime) {
        removeExpired(currentTime);
        return static_cast<int>(expiration_.size());
    }

private:
    void removeExpired(int currentTime) {
        while (!timeline_.empty() && timeline_.front().first <= currentTime) {
            auto [expirationTime, tokenId] = std::move(timeline_.front());
            timeline_.pop_front();

            auto it = expiration_.find(tokenId);
            if (it != expiration_.end() && it->second == expirationTime) {
                expiration_.erase(it);
            }
        }
    }

    int timeToLive_;
    std::unordered_map<std::string, int> expiration_;
    std::deque<std::pair<int, std::string>> timeline_;
};

generate() 为什么写两个容器

int expirationTime = currentTime + timeToLive_;
expiration_[tokenId] = expirationTime;
timeline_.emplace_back(expirationTime, std::move(tokenId));

哈希表负责回答“这个 token 当前是否有效、最新过期时间是多少”，时间队列负责回答“接下来应该清理谁”。只写其中一个容器，都无法同时高效完成这两类操作。

renew() 为什么先清理过期令牌

removeExpired(currentTime);
auto it = expiration_.find(tokenId);

题目规定过期令牌不能续期。如果不先清理，哈希表中可能仍然保留一个过期 token，程序就会错误地把它恢复为有效状态。清理之后，找不到 token 就直接返回。

有效 token 续期时，更新哈希表中的最新过期时间，并向时间队列追加新记录：

it->second = expirationTime;
timeline_.emplace_back(expirationTime, std::move(tokenId));

这里没有从队列中查找并删除旧记录，因为 deque 不支持根据 token $O(1)$ 定位。旧记录暂时保留，等它到达队首时再判断是否已经失效，这就是懒删除。

removeExpired() 中为什么必须比较过期时间

while (!timeline_.empty() && timeline_.front().first <= currentTime) {

当 expirationTime <= currentTime 时令牌已经过期。时间队列有序，所以只需不断检查队首；一旦队首尚未过期，后面的记录也都不需要处理。

弹出队首后不能直接执行 expiration_.erase(tokenId)，因为该队列记录可能是续期前留下的旧版本。例如：

token A 原过期时间：10
token A 续期后过期时间：20

timeline_:  (10, A), (20, A)
expiration_[A] = 20

当时间到达 10 时，队首的 (10, A) 已经过期，但 A 的最新版本仍有效。因此代码必须检查：

if (it != expiration_.end() && it->second == expirationTime) {
    expiration_.erase(it);
}

只有队列记录的过期时间等于哈希表中的最新过期时间，才能说明它代表当前版本并真正删除 token。如果二者不同，这只是一条续期前的陈旧记录，丢弃队列项即可。

countUnexpiredTokens() 为什么只返回哈希表大小

removeExpired(currentTime);
return static_cast<int>(expiration_.size());

先清理后，哈希表中只剩有效 token，并且每个 token 只保存一条最新状态，所以其大小就是未过期令牌数量。时间队列中可能包含旧版本，不能直接使用 timeline_.size()。

复杂度

哈希表操作平均为 $O(1)$。虽然一次 removeExpired() 可能弹出多条记录，但每条队列记录只会入队和出队一次，因此所有操作的均摊时间复杂度为 $O(1)$。空间不仅取决于当前有效 token 数量，也取决于尚未被弹出的续期旧记录数量。

全 O(1) 的数据结构

Leetcode 432. 设计一个数据结构，支持字符串计数的 inc、dec 操作，并能在 $O(1)$ 平均时间内返回计数最大和最小的任意字符串。

为什么普通哈希表不够

如果只使用 unordered_map<string, int>，inc() 和 dec() 很快，但每次获取最大或最小计数都要扫描所有 key，复杂度为 $O(n)$。为了让四个接口都达到平均 $O(1)$，需要直接维护计数的有序关系。

这里将计数相同的 key 放入同一个 bucket，并让 bucket 在双向链表中按照 count 严格递增：

front                                                    back
count = 1          count = 2          count = 5          count = 8
{a, c}     <->     {b}        <->     {d, e}     <->     {f}
最小计数                                                  最大计数

数据结构包括：

• list<Bucket> buckets_：维护 count 的递增顺序；
• Bucket::keys：用 unordered_set 保存该计数下的所有 key；
• positions_：key -> bucket 迭代器，可以直接找到 key 当前所在的计数桶。

链表中只保存非空 bucket。相邻 bucket 的 count 不要求连续，例如可以直接从 2 跳到 5。

class AllOne {
public:
    void inc(std::string key) {
        auto mapIt = positions_.find(key);
        if (mapIt == positions_.end()) {
            auto bucket = buckets_.begin();
            if (bucket == buckets_.end() || bucket->count != 1) {
                bucket = buckets_.insert(bucket, Bucket{1, {}});
            }
            bucket->keys.insert(key);
            positions_[std::move(key)] = bucket;
            return;
        }

        auto current = mapIt->second;
        auto next = std::next(current);
        if (next == buckets_.end() || next->count != current->count + 1) {
            next = buckets_.insert(next, Bucket{current->count + 1, {}});
        }

        next->keys.insert(key);
        mapIt->second = next;
        eraseFromBucket(current, key);
    }

    void dec(std::string key) {
        auto mapIt = positions_.find(key);
        auto current = mapIt->second;

        if (current->count == 1) {
            positions_.erase(mapIt);
        } else {
            auto previous = current == buckets_.begin()
                ? buckets_.end()
                : std::prev(current);

            if (previous == buckets_.end() ||
                previous->count != current->count - 1) {
                previous = buckets_.insert(
                    current, Bucket{current->count - 1, {}});
            }

            previous->keys.insert(key);
            mapIt->second = previous;
        }

        eraseFromBucket(current, key);
    }

    std::string getMaxKey() {
        return buckets_.empty() ? "" : *buckets_.back().keys.begin();
    }

    std::string getMinKey() {
        return buckets_.empty() ? "" : *buckets_.front().keys.begin();
    }

private:
    struct Bucket {
        int count;
        std::unordered_set<std::string> keys;
    };

    using BucketIterator = std::list<Bucket>::iterator;

    void eraseFromBucket(BucketIterator bucket, const std::string &key) {
        bucket->keys.erase(key);
        if (bucket->keys.empty()) {
            buckets_.erase(bucket);
        }
    }

    std::list<Bucket> buckets_;
    std::unordered_map<std::string, BucketIterator> positions_;
};

新 key 的 inc() 为什么放入 count 1

auto bucket = buckets_.begin();
if (bucket == buckets_.end() || bucket->count != 1) {
    bucket = buckets_.insert(bucket, Bucket{1, {}});
}

新 key 第一次出现，计数一定是 1。因为 bucket 按 count 递增，count 1 如果存在就只能位于链表头；如果头部不是 1，就在头部之前创建新 bucket。

bucket->keys.insert(key);
positions_[std::move(key)] = bucket;

将 key 放入 count 1 的集合，并在哈希表中记录 bucket 迭代器。以后不需要扫描链表就能找到它。

已有 key 的 inc() 为什么只检查下一个 bucket

假设 key 当前 count 为 c，增加后只可能变成 c + 1。由于链表有序，目标 bucket 如果存在，必然就是当前 bucket 的下一个节点：

auto current = mapIt->second;
auto next = std::next(current);

如果下一个 bucket 不存在，或者其 count 不是 c + 1，就在当前位置后创建：

next = buckets_.insert(next, Bucket{current->count + 1, {}});

随后完成三件事：

1. 将 key 插入新 bucket；
2. 将 positions_[key] 更新为新 bucket；
3. 从旧 bucket 删除 key，并在旧 bucket 为空时删除整个节点。

顺序上先取得并保存 current 和 next，再清理旧 bucket，避免删除旧节点后继续访问它。

dec() 为什么分 count 等于 1 和大于 1

如果当前 count 为 1，再减一次后 key 应从数据结构彻底消失：

positions_.erase(mapIt);

随后 eraseFromBucket() 从 count 1 bucket 中删除 key。

如果当前 count 大于 1，目标是 count - 1。它如果存在，只可能位于当前 bucket 的前一个位置：

auto previous = current == buckets_.begin()
    ? buckets_.end()
    : std::prev(current);

这里用 buckets_.end() 表示“当前节点前面没有 bucket”。如果前一个 bucket 不存在或 count 不等于 current->count - 1，就在当前节点之前创建目标 bucket。然后将 key 移入目标 bucket并更新 positions_。

题目保证调用 dec(key) 时 key 一定存在，所以代码没有额外处理 positions_.find(key) == positions_.end()。通用接口若不具备这个前提，应显式检查。

为什么最大值和最小值是 O(1)

return buckets_.empty() ? "" : *buckets_.back().keys.begin();
return buckets_.empty() ? "" : *buckets_.front().keys.begin();

链表头始终是最小 count，链表尾始终是最大 count。题目允许返回满足条件的任意 key，因此从对应 bucket 的 unordered_set 中取任意一个元素即可，不需要维护 bucket 内部顺序。

为什么必须删除空 bucket

bucket->keys.erase(key);
if (bucket->keys.empty()) {
    buckets_.erase(bucket);
}

如果保留空 bucket，front() 或 back() 可能指向一个没有 key 的计数，最小值和最大值接口就无法直接返回；相邻 bucket 查找也会遇到无效节点。因此链表中必须只保存非空 bucket。

复杂度和关键不变量

• 哈希表和 unordered_set 操作平均为 $O(1)$；
• 双向链表的相邻节点访问、插入和删除为 $O(1)$；
• inc()、dec()、getMaxKey()、getMinKey() 的平均时间复杂度均为 $O(1)$；
• 每个 key 只存在于一个 bucket 和一条 positions_ 记录中，空间复杂度为 $O(n)$。

必须始终保证：bucket 按 count 严格递增、bucket 非空、每个 key 只属于一个 bucket，并且 positions_[key] 与其实际 bucket 一致。

• 数据结构与算法