面试设计题不考"背 API"，考的是组合基础结构达成目标复杂度的能力。核心思路：
单一结构无法满足所有操作的复杂度要求时，用多个结构互补。
| 题目 | 目标 | 结构组合 |
|---|---|---|
| LC 380. O(1) 插入/删除/随机获取 | 三个操作均 O(1) | 数组 + 哈希表 |
| LC 155. 最小栈 | push/pop/min 均 O(1) | 主栈 + 辅助栈 |
| LC 460. LFU 缓存 | get/put O(1) | 哈希表 + 频率桶双向链表 |
| LC 232. 用栈实现队列 | 均摊 O(1) | 双栈 |
| LC 225. 用队列实现栈 | 单队列 O(1) push | 队列重排 |
graph LR Q[设计目标] --> S[单一结构不足] S --> C[多结构互补] C --> A[数组+哈希] C --> B[主栈+辅栈] C --> D[哈希+频率桶]
组合方案：数组存值 + 哈希表存「值→数组下标」。删除时把目标元素和末尾元素交换，然后弹出末尾。
class RandomizedSet {
private List<Integer> nums = new ArrayList<>();
private Map<Integer, Integer> indexMap = new HashMap<>();
private Random rand = new Random();
public boolean insert(int val) {
if (indexMap.containsKey(val)) return false;
indexMap.put(val, nums.size());
nums.add(val);
return true;
}
public boolean remove(int val) {
Integer idx = indexMap.get(val);
if (idx == null) return false;
// 与末尾交换
int last = nums.get(nums.size() - 1);
nums.set(idx, last);
indexMap.put(last, idx);
nums.remove(nums.size() - 1);
indexMap.remove(val);
return true;
}
public int getRandom() {
return nums.get(rand.nextInt(nums.size()));
}
}关键细节：删除时若目标就是末尾元素，交换操作退化为直接弹出，逻辑仍然正确。
辅助栈与主栈同步，辅助栈栈顶始终是当前主栈的最小值。
class MinStack {
private stack: number[] = [];
private minStack: number[] = [];
push(val: number): void {
this.stack.push(val);
this.minStack.push(
this.minStack.length === 0
? val
: Math.min(val, this.minStack[this.minStack.length - 1])
);
}
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];
}
}优化：辅助栈只在新最小值出现时入栈（但要处理重复最小值的弹出问题）。
| 策略 | 淘汰依据 | 结构 |
|---|---|---|
| LRU | 最久未使用 | 哈希 + 双向链表 |
| LFU | 使用频率最低（同频取最旧） | 哈希 + 频率桶链表 |
keyToNode: Map<key, Node> // O(1) 定位节点
freqToList: Map<freq, DoublyList> // 每个频率一个双向链表
minFreq: number // 当前最低频率（淘汰用）
class Node {
key: number; val: number; freq: number;
prev: Node | null = null; next: Node | null = null;
constructor(key: number, val: number) {
this.key = key; this.val = val; this.freq = 1;
}
}
class DoublyList {
head = new Node(0, 0);
tail = new Node(0, 0);
size = 0;
constructor() { this.head.next = this.tail; this.tail.prev = this.head; }
addToHead(node: Node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next!.prev = node;
this.head.next = node;
this.size++;
}
remove(node: Node) {
node.prev!.next = node.next;
node.next!.prev = node.prev;
this.size--;
}
removeLast(): Node | null {
if (this.size === 0) return null;
const last = this.tail.prev!;
this.remove(last);
return last;
}
}
class LFUCache {
private capacity: number;
private minFreq = 0;
private keyToNode = new Map<number, Node>();
private freqToList = new Map<number, DoublyList>();
constructor(capacity: number) { this.capacity = capacity; }
get(key: number): number {
const node = this.keyToNode.get(key);
if (!node) return -1;
this.touch(node);
return node.val;
}
put(key: number, value: number): void {
if (this.capacity <= 0) return;
const existing = this.keyToNode.get(key);
if (existing) {
existing.val = value;
this.touch(existing);
return;
}
if (this.keyToNode.size >= this.capacity) {
const list = this.freqToList.get(this.minFreq)!;
const evicted = list.removeLast()!;
this.keyToNode.delete(evicted.key);
}
const node = new Node(key, value);
this.keyToNode.set(key, node);
if (!this.freqToList.has(1)) this.freqToList.set(1, new DoublyList());
this.freqToList.get(1)!.addToHead(node);
this.minFreq = 1;
}
private touch(node: Node) {
const oldList = this.freqToList.get(node.freq)!;
oldList.remove(node);
if (node.freq === this.minFreq && oldList.size === 0) this.minFreq++;
node.freq++;
if (!this.freqToList.has(node.freq)) this.freqToList.set(node.freq, new DoublyList());
this.freqToList.get(node.freq)!.addToHead(node);
}
}
复杂度：get/put 均 O(1)。
双栈：输入栈 + 输出栈。输出栈空时把输入栈全部倒入：
class MyQueue {
private inStack: number[] = [];
private outStack: number[] = [];
push(x: number): void { this.inStack.push(x); }
pop(): number {
this.peek();
return this.outStack.pop()!;
}
peek(): number {
if (this.outStack.length === 0) {
while (this.inStack.length > 0) {
this.outStack.push(this.inStack.pop()!);
}
}
return this.outStack[this.outStack.length - 1];
}
empty(): boolean {
return this.inStack.length === 0 && this.outStack.length === 0;
}
}
均摊分析：每个元素最多被倒一次，均摊 O(1)。
单队列：每次 push 后，把之前的元素全部重新排到新元素后面：
class MyStack {
private queue: number[] = [];
push(x: number): void {
this.queue.push(x);
const size = this.queue.length;
for (let i = 0; i < size - 1; i++) {
this.queue.push(this.queue.shift()!);
}
}
pop(): number { return this.queue.shift()!; }
top(): number { return this.queue[0]; }
empty(): boolean { return this.queue.length === 0; }
}
遇到设计题按以下步骤思考：
| 步骤 | 问题 |
|---|---|
| 1. 列操作 | 每个操作的目标复杂度是什么？ |
| 2. 找矛盾 | 哪个操作用单一结构达不到？ |
| 3. 组合结构 | 用什么辅助结构弥补？ |
| 4. 定同步规则 | 两个结构之间何时同步、谁为准？ |
| 5. 验证边界 | 空结构、重复元素、容量满 |