1269 字
6 分钟
设计题：从设计模式到高频数据结构设计
概述
数据结构设计题 要求在指定操作和复杂度约束下，组合已有数据结构实现新的抽象。重点不是写一个函数，而是维护对象内部状态，让每个方法都满足时间和空间要求。
前置知识
- 栈、哈希表、链表：高频设计题的基础组件
- 复杂度约束：每个 API 都要单独分析
- 不变量：对象内部状态必须在每次操作后保持一致
问题定义
给定一组 API 和复杂度要求，设计类的内部数据结构，使所有操作都能正确、高效地执行。
| 要素 | 说明 |
|---|---|
| 输入 | 构造参数和一组方法调用 |
| 输出 | 每个方法的返回值和对象状态变化 |
| 核心约束 | get、put、push、pop 等操作复杂度 |
| 典型问题 | 最小栈、哈希集合、LRU 缓存、LFU 缓存 |
核心原理：分步图解
以 LRU 缓存为例，哈希表负责 O(1) 定位节点，双向链表负责 O(1) 移动和淘汰：
graph LR
M[Map key -> Node] --> A[head]
A --> B[最近使用]
B --> C[较旧]
C --> D[tail]每次 get 或更新已有 key，都把节点移动到链表头部；容量超限时，从尾部删除最久未使用节点。
算法精细步骤
算法：LRUCache.put(key, value)输入：键和值输出：无
1. 如果 key 已存在：2. 更新节点值3. 将节点移动到链表头部4. 返回5. 创建新节点并加入 Map6. 将新节点插入链表头部7. 如果容量超限：8. 删除链表尾部节点9. 从 Map 中删除对应 key复杂度分析：
| 结构 | 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 最小栈 | push/pop/top/getMin | O(1) | O(n) |
| 哈希集合 | add/remove/contains | 平均 O(1) | O(n) |
| LRU 缓存 | get/put | O(1) | O(capacity) |
| LFU 缓存 | get/put | O(1) 均摊 | O(capacity) |
TypeScript 实现
1. 最小栈
class MinStack { private stack: number[] = []; private minStack: number[] = [];
push(value: number): void { this.stack.push(value); const min = this.minStack.length === 0 ? value : Math.min(value, this.minStack[this.minStack.length - 1]); this.minStack.push(min); }
pop(): void { this.stack.pop(); this.minStack.pop(); }
top(): number { return this.stack[this.stack.length - 1]; }
getMin(): number { return this.minStack[this.minStack.length - 1]; }}2. 哈希集合
class MyHashSet { private readonly size = 769; private buckets: number[][] = Array.from({ length: 769 }, () => []);
private hash(key: number): number { return key % this.size; }
add(key: number): void { const bucket = this.buckets[this.hash(key)]; if (!bucket.includes(key)) bucket.push(key); }
remove(key: number): void { const bucket = this.buckets[this.hash(key)]; const index = bucket.indexOf(key); if (index !== -1) bucket.splice(index, 1); }
contains(key: number): boolean { return this.buckets[this.hash(key)].includes(key); }}3. LRU 节点
class DLinkedNode { key: number; value: number; prev: DLinkedNode | null = null; next: DLinkedNode | null = null;
constructor(key: number, value: number) { this.key = key; this.value = value; }}4. LRU 缓存
class LRUCache { private cache = new Map<number, DLinkedNode>(); private head = new DLinkedNode(0, 0); private tail = new DLinkedNode(0, 0);
constructor(private capacity: number) { this.head.next = this.tail; this.tail.prev = this.head; }
get(key: number): number { const node = this.cache.get(key); if (!node) return -1;
this.moveToHead(node); return node.value; }
put(key: number, value: number): void { const existing = this.cache.get(key); if (existing) { existing.value = value; this.moveToHead(existing); return; }
const node = new DLinkedNode(key, value); this.cache.set(key, node); this.addToHead(node);
if (this.cache.size > this.capacity) { const removed = this.removeTail(); this.cache.delete(removed.key); } }
private addToHead(node: DLinkedNode): void { node.prev = this.head; node.next = this.head.next; this.head.next!.prev = node; this.head.next = node; }
private removeNode(node: DLinkedNode): void { node.prev!.next = node.next; node.next!.prev = node.prev; }
private moveToHead(node: DLinkedNode): void { this.removeNode(node); this.addToHead(node); }
private removeTail(): DLinkedNode { const node = this.tail.prev!; this.removeNode(node); return node; }}5. LFU 缓存简化实现
interface LFUNode { key: number; value: number; freq: number;}
class LFUCache { private minFreq = 0; private keyToNode = new Map<number, LFUNode>(); private freqToKeys = new Map<number, Set<number>>();
constructor(private capacity: number) {}
get(key: number): number { const node = this.keyToNode.get(key); if (!node) return -1;
this.increaseFreq(key); return node.value; }
put(key: number, value: number): void { if (this.capacity === 0) return;
const node = this.keyToNode.get(key); if (node) { node.value = value; this.increaseFreq(key); return; }
if (this.keyToNode.size >= this.capacity) { const evictKey = this.freqToKeys.get(this.minFreq)!.values().next().value; this.freqToKeys.get(this.minFreq)!.delete(evictKey); this.keyToNode.delete(evictKey); }
this.keyToNode.set(key, { key, value, freq: 1 }); if (!this.freqToKeys.has(1)) this.freqToKeys.set(1, new Set()); this.freqToKeys.get(1)!.add(key); this.minFreq = 1; }
private increaseFreq(key: number): void { const node = this.keyToNode.get(key)!; const oldKeys = this.freqToKeys.get(node.freq)!; oldKeys.delete(key);
if (oldKeys.size === 0 && node.freq === this.minFreq) { this.minFreq++; }
node.freq++; if (!this.freqToKeys.has(node.freq)) this.freqToKeys.set(node.freq, new Set()); this.freqToKeys.get(node.freq)!.add(key); }}工程优化：用不变量管理状态
| 设计题 | 核心不变量 | 辅助结构 |
|---|---|---|
| 最小栈 | minStack[i] 存储前 i 层最小值 | 辅助栈 |
| 哈希集合 | 同一 bucket 中不重复存 key | 桶数组 |
| LRU | 链表头部最新，尾部最旧 | Map + 双向链表 |
| LFU | minFreq 始终指向最小访问频率 | keyMap + freqMap |
写设计题时，先列 API，再列每个 API 后必须保持的不变量，比直接写代码更稳。
应用与局限
典型应用
- 缓存淘汰策略：LRU、LFU
- 栈/队列增强结构：最小栈、单调队列
- 哈希结构：集合、映射、计数器
- 业务对象状态机和资源池管理
局限性
| 局限 | 说明 |
|---|---|
| 状态耦合高 | 多个结构必须同步更新 |
| 边界多 | 空容量、重复 key、删除尾节点都要保持一致 |
| 实现复杂度高 | O(1) 要求通常需要组合多个结构 |
总结
graph LR
A[明确 API] --> B[分析复杂度要求]
B --> C[选择基础结构]
C --> D[定义不变量]
D --> E[实现并维护状态同步]核心要点：
- 设计题的核心是用已有数据结构组合出新的操作语义。
- 每个方法都要单独满足复杂度要求。
- Map 负责快速定位，链表负责快速调整顺序，是缓存题的常见组合。
- 内部不变量比代码模板更重要。
设计题：从设计模式到高频数据结构设计
https://www.hehonglei.cn/technology/design/