摘要

LeetCode 432 是一题非常经典的“设计题”——要求你构建一个数据结构，支持：

• 插入 / 删除 / 更新字符串计数
• 在 O(1) 时间内得到最大计数 key 和最小计数 key

也就是说，你得在常数时间内维护一张「字符串频次表」，还要能快速拿到当前最高频和最低频的 key。
这类题通常考的是：**哈希表 + 双向链表（Bucket List）**的组合拳。

如果你之前写过 LRU Cache，那这题就是同一个风格，但把重点从“最近使用”变成了“频次桶”。

描述

我们要实现一个如下接口的类 AllOne：

• inc(key): 字符串 key 的计数 +1（不存在则变成 1）
• dec(key): 字符串 key 的计数 −1（为 0 就删掉）
• getMaxKey(): 任意返回一个当前出现次数最多的 key
• getMinKey(): 任意返回一个当前出现次数最少的 key

所有操作必须达到 O(1) 时间复杂度。

这个要求意味着：

• 不能排序
• 不能遍历所有 key
• 不能扫描所有桶

我们需要某种结构，能随着频次变化自动“换桶”，并且头尾节点就代表最小/最大频。

于是就有了主流方案：双向链表维护频次桶，每个桶里装所有相同频次的 key，HashMap 记录每个 key 当前所在的桶。
这样所有增减操作都只是局部调整指针与插入集合。

题解答案（思路总结）

核心组件：

1. Double Linked List（双向链表桶）

   • 每个节点 Bucket 代表一种频次
   • Bucket.count 表示频次
   • Bucket.keys 是一个 Set<String>，记录所有该频次的 key
   • 双向链表从小频次到大频次排列

2. HashMap

   • keyToBucket[key] = bucketNode
   • 查询 key 当前在哪里：O(1)
   • 修改 key 频次 = 移动到前一个/后一个 bucket

3. O(1) 关键点

   • 查找桶：O(1)
   • 移动桶：O(1)
   • 新增/删除桶：O(1)
   • 删除 key：O(1)
   • 获取最大 / 最小频 key：链表尾 / 链表头：O(1)

这套“桶链表 + Key 定位”思路是必杀技。

题解代码分析（完整 Swift 可运行 Demo）

以下代码能直接运行（Swift 5+）。

import Foundation

// MARK: - Bucket 链表节点
class Bucket {
    var count: Int
    var keys: Set<String>
    var prev: Bucket?
    var next: Bucket?
    
    init(_ count: Int) {
        self.count = count
        self.keys = Set<String>()
    }
}

// MARK: - AllOne 主类
class AllOne {
    
    private var head: Bucket?    // 最小 count 的 bucket
    private var tail: Bucket?    // 最大 count 的 bucket
    private var keyToBucket: [String: Bucket] = [:]
    
    init() {}
    
    // MARK: - inc
    func inc(_ key: String) {
        if let bucket = keyToBucket[key] {
            moveKey(key, from: bucket, toCount: bucket.count + 1)
        } else {
            // key 不存在 -> 放入 count = 1 的 bucket
            if head?.count == 1 {
                head?.keys.insert(key)
                keyToBucket[key] = head
            } else {
                // 创建新的 bucket = 1
                let newBucket = Bucket(1)
                newBucket.keys.insert(key)
                insertBefore(newBucket, before: head)
                head = newBucket
                if tail == nil { tail = newBucket }
                keyToBucket[key] = newBucket
            }
        }
    }
    
    // MARK: - dec
    func dec(_ key: String) {
        guard let bucket = keyToBucket[key] else { return }
        let oldCount = bucket.count
        
        if oldCount == 1 {
            // 删除 key
            bucket.keys.remove(key)
            keyToBucket[key] = nil
            if bucket.keys.isEmpty { removeBucket(bucket) }
            return
        }
        
        // 移动到 oldCount - 1 的 bucket
        moveKey(key, from: bucket, toCount: oldCount - 1)
    }
    
    // MARK: - 获取最大 key
    func getMaxKey() -> String {
        return tail?.keys.first ?? ""
    }
    
    // MARK: - 获取最小 key
    func getMinKey() -> String {
        return head?.keys.first ?? ""
    }
    
    // MARK: - 工具方法：移动 key 到新的频次 bucket
    private func moveKey(_ key: String, from bucket: Bucket, toCount: Int) {
        bucket.keys.remove(key)
        
        var targetBucket: Bucket?
        
        if toCount > bucket.count {
            // 向右找（higher bucket）
            if let next = bucket.next, next.count == toCount {
                targetBucket = next
            } else {
                // 创建新 bucket（在 bucket 之后）
                let newBucket = Bucket(toCount)
                insertAfter(newBucket, after: bucket)
                if bucket === tail { tail = newBucket }
                targetBucket = newBucket
            }
        } else {
            // 向左找（lower bucket）
            if let prev = bucket.prev, prev.count == toCount {
                targetBucket = prev
            } else {
                let newBucket = Bucket(toCount)
                insertBefore(newBucket, before: bucket)
                if bucket === head { head = newBucket }
                targetBucket = newBucket
            }
        }
        
        targetBucket?.keys.insert(key)
        keyToBucket[key] = targetBucket
        
        // 原 bucket 空了就删掉
        if bucket.keys.isEmpty {
            removeBucket(bucket)
        }
    }
    
    // MARK: - 链表操作：插入
    private func insertBefore(_ new: Bucket, before node: Bucket?) {
        new.next = node
        new.prev = node?.prev
        node?.prev?.next = new
        node?.prev = new
        
        if node === head {
            head = new
        }
        if tail == nil {
            tail = new
        }
    }
    
    private func insertAfter(_ new: Bucket, after node: Bucket) {
        new.prev = node
        new.next = node.next
        node.next?.prev = new
        node.next = new
        
        if node === tail {
            tail = new
        }
    }
    
    // MARK: - 链表操作：删除 bucket
    private func removeBucket(_ bucket: Bucket) {
        let prev = bucket.prev
        let next = bucket.next
        
        prev?.next = next
        next?.prev = prev
        
        if bucket === head { head = next }
        if bucket === tail { tail = prev }
        
        bucket.prev = nil
        bucket.next = nil
    }
}

// MARK: - Demo 测试
let allOne = AllOne()
allOne.inc("hello")
allOne.inc("hello")
print(allOne.getMaxKey())  // hello
print(allOne.getMinKey())  // hello
allOne.inc("leet")
print(allOne.getMaxKey())  // hello
print(allOne.getMinKey())  // leet

示例测试及结果

运行上面 Demo 输出：

hello
hello
hello
leet

这正好对应题目示例：

• “hello” 加两次，计数最高、也是唯一，所以 max 和 min 都是它
• 后面再 insert “leet”，则 minKey 变成 “leet”，maxKey 还是 “hello”

你可以再手动多写几个测试，比如：

allOne.inc("a")
allOne.inc("b")
allOne.inc("b")
allOne.inc("c")
allOne.inc("c")
allOne.inc("c")
print(allOne.getMaxKey())  // c
print(allOne.getMinKey())  // a

数据结构能自动维持桶的顺序与频次变化。

时间复杂度

所有操作均满足 O(1)：

• inc：通过 HashMap 定位 bucket，然后在链表中局部移动 → O(1)
• dec：同理 → O(1)
• getMaxKey / getMinKey：直接取 tail/head → O(1)
• 插入 / 删除桶都是链表常量时间 → O(1)

空间复杂度

• HashMap keyToBucket 存每个 key → O(N)
• Bucket 链表最多有 N 个不同频次 → O(N)
• 每个 bucket 的 key 集合加总仍是所有 key → O(N)

总空间复杂度：O(N)

总结

LeetCode 432 是设计题里颇有代表性的题目。如果你能把这题吃透，後續遇到需要 O(1) 维护「最值、最大、最小、频次」的场景，基本都能套用：

• HashMap 存 key 的位置
• 双向链表作为序结构（频次、优先级、权重…）
• 局部移动桶节点实现常量复杂度更新