LeetCode 432. 全 O(1) 的数据结构

2022-08-23 HGNULB 约 14 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 432. 全 O(1) 的数据结构

题意分析

要维护一批字符串各自的出现次数，并支持四种操作：给某个字符串的计数加一、减一，以及随时报出当前计数最大和计数最小的任意一个字符串。

约束里最刺眼的一条是「每个操作平均时间复杂度 $O(1)$」。这句话直接否掉了任何需要在操作时扫描全部 key、或者依赖比较排序结构的做法，逼着我们把「谁最大、谁最小」这件事变成可以直接读出来的常量级查询。

边界有几处要留意：dec 作用在计数为 $1$ 的 key 上时，这个 key 应当彻底消失，而不是留下一个计数为 $0$ 的残留；题目保证 dec 只会作用在已存在的 key 上，但实现上多一层判空更稳；当结构为空时，getMaxKey 与 getMinKey 都返回空字符串；同一个计数可能被很多 key 共享，所以「计数最大的 key」不唯一，返回其中任意一个都算对。

解法：双向链表 + 哈希表

核心思路

最直接的写法是一张 key -> count 的哈希表。inc 和 dec 确实是 $O(1)$，但 getMaxKey 只能遍历整张表挑出最大计数，退化成 $O(n)$。换成有序结构（如平衡树按计数排序）能让查询变成 $O(\log n)$，仍然够不到题目要的 $O(1)$。

瓶颈在于「按计数排序」这件事被当成了一个每次都要重新求解的通用问题。但这里的修改极其温和：一次 inc 只把某个 key 的计数从 $c$ 变成 $c+1$，一次 dec 只把它从 $c$ 变成 $c-1$。也就是说，元素在「按计数排好的序列」里每次至多挪动一格。既然只挪一格，就没必要重新排序，顺着指针走一步就够了。

由此得到的组织方式是：把计数相同的 key 打包成一个「桶」，桶按计数从小到大用双向链表串起来。整个结构维持两条不变量。其一，链表从 head 到 tail 的方向上，桶的计数严格递增，且链表中不存在 keys 为空的桶——因此 head.next 永远是当前最小计数的桶，tail.prev 永远是当前最大计数的桶，两个查询各取一个元素即可。其二，哈希表 nodes 中 key 到桶的映射始终指向那个真正包含该 key 的桶，于是从任意 key 出发都能在 $O(1)$ 内定位它在链表中的位置，再顺着 prev / next 走一格完成搬迁。

桶内用集合而不是链表存 key，是为了让「从旧桶删除某个 key」也保持 $O(1)$。

解题步骤

建立带哨兵的双向链表：head 和 tail 两个空桶首尾相接。有了哨兵，插入和删除就不必区分「链表为空」「插在头部」「插在尾部」这些情况，所有指针操作都能统一成四行赋值。

inc(key) 时先查 nodes。若 key 不存在，它的目标计数是 $1$，目标位置只可能是链表最前端：看 head.next 是不是一个计数为 $1$ 的真实桶，是就直接塞进去，否则新建一个计数为 $1$ 的桶插在 head 之后。之所以只需要检查 head.next 而不用查找，是因为不变量保证计数为 $1$ 的桶若存在，必定就在最前面。

若 key 已存在，取出它当前所在的桶 cur，目标计数是 cur.count + 1。由于链表计数严格递增，计数为该值的桶如果存在，必定就是 cur.next。于是检查 cur.next：计数匹配就并入，否则新建一个桶插在 cur 之后。这一步是「只挪一格」这个观察的直接兑现。

搬迁完成后，从 cur 的集合里删掉 key；如果 cur 变空就把它从链表摘掉。必须删空桶，否则「链表首尾即最值」这条不变量立刻失效——一个残留的空桶会让 getMinKey 取到不存在的元素。注意顺序：先把 key 加进新桶并更新 nodes，再从旧桶删除，这样即使新旧桶是同一个引用也不会误删。

dec(key) 对称处理，只是多了一个终止情况：当 cur.count == 1 时，减一后计数归零，这个 key 应当整体消失，所以从桶集合和 nodes 里同时删除，而不是搬到某个「计数为 $0$」的桶里。其余情况看 cur.prev 是否是计数为 cur.count - 1 的真实桶，是则并入，否则新建桶插在 cur.prev 之后。

getMaxKey 判断 tail.prev == head（链表为空）后返回 tail.prev 桶中任意一个 key；getMinKey 判断 head.next == tail 后返回 head.next 桶中任意一个 key。

以 inc("hello")、inc("hello")、getMaxKey、getMinKey、inc("leet")、getMaxKey、getMinKey 走一遍：初始链表是 head <-> tail，nodes 为空。第一次 inc("hello")，key 不在 nodes 中，head.next 就是 tail，不是真实桶，于是新建桶 $B_1$（计数 $1$，keys 为 {hello}）插在 head 之后，链表变成 head <-> B1(1:{hello}) <-> tail，nodes = {hello -> B1}。第二次 inc("hello")，key 已存在，cur = B1，目标计数 $2$，cur.next 是 tail 不匹配，于是新建桶 $B_2$（计数 $2$，keys 为 {hello}）插在 $B_1$ 之后并更新 nodes = {hello -> B2}；随后从 $B_1$ 删除 hello，$B_1$ 变空被摘除，链表成为 head <-> B2(2:{hello}) <-> tail。此时 getMaxKey 取 tail.prev = B2，返回 "hello"；getMinKey 取 head.next = B2，同样返回 "hello"。接着 inc("leet")，key 不在 nodes 中，检查 head.next = B2，它是真实桶但计数为 $2$ 而非 $1$，于是新建桶 $B_3$（计数 $1$，keys 为 {leet}）插在 head 之后，链表成为 head <-> B3(1:{leet}) <-> B2(2:{hello}) <-> tail，nodes = {hello -> B2, leet -> B3}。最后 getMaxKey 取 tail.prev = B2，返回 "hello"；getMinKey 取 head.next = B3，返回 "leet"。

代码实现

// key -> bucket 的哈希表用于 O(1) 找到 key 所在桶。
class AllOne {
    private final Bucket head;
    private final Bucket tail;
    private final Map<String, Bucket> nodes;

    public AllOne() {
        head = new Bucket(0);
        tail = new Bucket(0);
        head.next = tail;
        tail.prev = head;
        nodes = new HashMap<>();
    }

    public void inc(String key) {
        if (!nodes.containsKey(key)) {
            Bucket first = head.next;
            if (first != tail && first.count == 1) {
                first.keys.add(key);
                nodes.put(key, first);
            } else {
                Bucket bucket = new Bucket(1);
                bucket.keys.add(key);
                insertAfter(head, bucket);
                nodes.put(key, bucket);
            }
            return;
        }

        Bucket cur = nodes.get(key);
        Bucket next = cur.next;
        int nextCount = cur.count + 1;

        if (next != tail && next.count == nextCount) {
            next.keys.add(key);
            nodes.put(key, next);
        } else {
            Bucket bucket = new Bucket(nextCount);
            bucket.keys.add(key);
            insertAfter(cur, bucket);
            nodes.put(key, bucket);
        }

        cur.keys.remove(key);
        if (cur.keys.isEmpty()) {
            remove(cur);
        }
    }

    public void dec(String key) {
        Bucket cur = nodes.get(key);
        if (cur == null) {
            return;
        }

        if (cur.count == 1) {
            cur.keys.remove(key);
            nodes.remove(key);
            if (cur.keys.isEmpty()) {
                remove(cur);
            }
            return;
        }

        Bucket prev = cur.prev;
        int prevCount = cur.count - 1;

        if (prev != head && prev.count == prevCount) {
            prev.keys.add(key);
            nodes.put(key, prev);
        } else {
            Bucket bucket = new Bucket(prevCount);
            bucket.keys.add(key);
            insertAfter(prev, bucket);
            nodes.put(key, bucket);
        }

        cur.keys.remove(key);
        if (cur.keys.isEmpty()) {
            remove(cur);
        }
    }

    public String getMaxKey() {
        if (tail.prev == head) {
            return "";
        }
        return tail.prev.keys.iterator().next();
    }

    public String getMinKey() {
        if (head.next == tail) {
            return "";
        }
        return head.next.keys.iterator().next();
    }

    private void insertAfter(Bucket node, Bucket add) {
        add.prev = node;
        add.next = node.next;
        node.next.prev = add;
        node.next = add;
    }

    private void remove(Bucket node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private static class Bucket {
        int count;
        Set<String> keys = new HashSet<>();
        Bucket prev;
        Bucket next;

        Bucket(int count) {
            this.count = count;
        }
    }
}

// key -> bucket 的哈希表用于 O(1) 找到 key 所在桶。
type Bucket struct {
    count int
    keys  map[string]struct{}
    prev  *Bucket
    next  *Bucket
}

type AllOne struct {
    head  *Bucket
    tail  *Bucket
    nodes map[string]*Bucket
}

func Constructor() AllOne {
    head := &Bucket{count: 0, keys: make(map[string]struct{})}
    tail := &Bucket{count: 0, keys: make(map[string]struct{})}
    head.next = tail
    tail.prev = head

    return AllOne{head: head, tail: tail, nodes: make(map[string]*Bucket)}
}

func (a *AllOne) Inc(key string) {
    if _, ok := a.nodes[key]; !ok {
        first := a.head.next
        if first != a.tail && first.count == 1 {
            first.keys[key] = struct{}{}
            a.nodes[key] = first
        } else {
            bucket := &Bucket{count: 1, keys: make(map[string]struct{})}
            bucket.keys[key] = struct{}{}
            a.insertAfter(a.head, bucket)
            a.nodes[key] = bucket
        }
        return
    }

    cur := a.nodes[key]
    next := cur.next
    nextCount := cur.count + 1

    if next != a.tail && next.count == nextCount {
        next.keys[key] = struct{}{}
        a.nodes[key] = next
    } else {
        bucket := &Bucket{count: nextCount, keys: make(map[string]struct{})}
        bucket.keys[key] = struct{}{}
        a.insertAfter(cur, bucket)
        a.nodes[key] = bucket
    }

    delete(cur.keys, key)
    if len(cur.keys) == 0 {
        a.remove(cur)
    }
}

func (a *AllOne) Dec(key string) {
    cur, ok := a.nodes[key]
    if !ok {
        return
    }

    if cur.count == 1 {
        delete(cur.keys, key)
        delete(a.nodes, key)
        if len(cur.keys) == 0 {
            a.remove(cur)
        }
        return
    }

    prev := cur.prev
    prevCount := cur.count - 1

    if prev != a.head && prev.count == prevCount {
        prev.keys[key] = struct{}{}
        a.nodes[key] = prev
    } else {
        bucket := &Bucket{count: prevCount, keys: make(map[string]struct{})}
        bucket.keys[key] = struct{}{}
        a.insertAfter(prev, bucket)
        a.nodes[key] = bucket
    }

    delete(cur.keys, key)
    if len(cur.keys) == 0 {
        a.remove(cur)
    }
}

func (a *AllOne) GetMaxKey() string {
    if a.tail.prev == a.head {
        return ""
    }
    for k := range a.tail.prev.keys {
        return k
    }
    return ""
}

func (a *AllOne) GetMinKey() string {
    if a.head.next == a.tail {
        return ""
    }
    for k := range a.head.next.keys {
        return k
    }
    return ""
}

func (a *AllOne) insertAfter(node *Bucket, add *Bucket) {
    add.prev = node
    add.next = node.next
    node.next.prev = add
    node.next = add
}

func (a *AllOne) remove(node *Bucket) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

复杂度分析

时间复杂度：四个操作均为 $O(1)$。定位 key 靠哈希表一次查询；搬迁只看相邻的一个桶，指针改动是常数条；插入与摘除桶各是四次指针赋值；取最值直接读哨兵的邻居。全程没有任何与 $n$ 相关的遍历。

空间复杂度：$O(n)$，$n$ 为当前存活的不同 key 数量。哈希表存 $n$ 条映射；桶的个数不会超过不同计数的种类数，而不同计数种类数不超过 $n$，因此链表规模同样是 $O(n)$；所有桶集合中的 key 总数恰为 $n$。

关键点总结

当一个查询要求 $O(1)$ 而朴素做法是 $O(n)$ 扫描时，思路应当从「怎么更快地找」转向「怎么让答案一直待在固定位置」。这里就是把最值钉死在链表首尾。

修改的局部性是设计的关键前提。计数每次只变化 $1$，元素在有序序列里至多挪一格，这才让「顺指针走一步」取代了重新排序。若题目改成一次加任意值，这套结构就不成立了。

相同状态的元素合并成桶，桶之间有序、桶内无序，是一类高频设计模式。判断依据是：题目只关心「某个状态的代表元」，不关心同状态元素之间的次序。

不变量必须在每次操作后立即恢复。「链表中无空桶」这条如果偷懒不维护，首尾即最值的结论马上崩塌，而且错误会延后很久才暴露。

面试视角：这题的考点不是想出结构，而是把指针操作写干净。哨兵节点、先插新桶再删旧 key 的顺序、dec 归零的特判，是面试官会逐个盯的地方。写完主动说清两条不变量并挑一两个操作口述验证，比闷头写完更能体现设计能力。

面试视角：能顺势对比 LRU 与 LFU 的结构选择会加分——三者都是「哈希表定位 + 链表维序」，区别只在链表上排的是时间、频次还是计数。

易错点总结

错误写法：inc 时先从旧桶删除 key 再加入新桶 → 当新桶恰好就是旧桶（某些变体实现里会出现自环判断）或删除后旧桶被提前摘除导致 insertAfter 拿到已脱链的节点时，链表结构被破坏，后续 getMinKey 读到游离节点。

错误写法：搬迁后忘记检查旧桶是否为空并摘除 → 执行 inc("a")、inc("a") 后链表里残留一个计数为 $1$ 的空桶，getMinKey 从空集合取元素，抛异常或返回错误的空串。

错误写法：dec 在 count == 1 时新建一个计数为 $0$ 的桶 → 执行 inc("a")、dec("a")、getMinKey 时链表里挂着计数为 $0$ 的桶，返回 "a"，而正确答案是空字符串。

错误写法：getMaxKey / getMinKey 不判断链表为空 → 结构为空时 tail.prev 是哨兵 head，从它的空集合取元素直接崩溃，正确行为是返回 ""。

错误写法：检查相邻桶时只比较计数、不排除哨兵 → head 与 tail 的 count 字段是 $0$，当某个桶计数为 $1$ 且执行 dec 时，prev 恰是 head 且 count 匹配 $0$，key 会被塞进哨兵桶，整个结构污染。

错误写法：桶内用链表或数组存 key → 从旧桶删除某个 key 需要线性查找，单次操作退化成 $O(n)$，正好违背题目唯一的硬约束。

错误写法：搬迁后忘记更新 nodes 中 key 指向的新桶 → 下一次对同一个 key 的 inc 会从旧桶（可能已被摘除）出发，计数从此停止增长且链表逐渐脱节。

错误写法：dec 一个不存在的 key 时不做判空直接解引用 → 空指针崩溃；虽然题目声明不会这样调用，但多写一行判空是零成本的防御。

错误写法：新 key 的 inc 直接无条件新建计数为 $1$ 的桶插在 head 之后 → 依次 inc("a")、inc("b") 会产生两个计数都为 $1$ 的桶，破坏「计数严格递增」的不变量，之后 dec 时相邻桶的匹配判断开始失灵。

错误写法：用一张 count -> 桶 的哈希表替代链表来找相邻桶 → 找相邻桶本身是 $O(1)$ 了，但 getMaxKey 需要知道当前最大计数是多少，仍然得维护有序信息，绕回原点。

相似题目

题目	难度	考察点
460. LFU 缓存	困难	同样按频次分桶，但需额外在桶内维护时间顺序以打破平局
146. LRU 缓存	中等	链表上排的是访问时间而非计数，只需把节点整体挪到头部
895. 最大频率栈	困难	按频次分组但用栈保序，弹出后频次回落，无需删除中间元素
380. O(1) 时间插入、删除和获取随机元素	中等	常数级随机访问靠数组换位实现，与桶链表是另一条思路
155. 最小栈	中等	最值查询受限于栈的后进先出，可用辅助栈同步记录而非排序结构