LeetCode 设计题实战指南六道经典数据结构设计题的 Trade-off 与解题套路【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode设计题Design是一类没有标准答案的开放性问题其核心不在于算法本身的精巧而在于针对特定问题的设计选择即所谓的 trade-off。本文基于本仓库的设计题讲义英文原稿 与中文讲义完整讲解讲义精选的 6 道设计题——最小栈、单词词典、双栈队列、LFU 缓存、最大频率栈与 RLE 迭代器——的数据结构选型思路、关键代码与复杂度权衡帮助你建立应对设计题的方法论先定 API 复杂度目标再反推数据结构最后处理平局tie-break规则。一、什么是设计题开放性问题与 Trade-off 思维设计题讲义开宗明义地指出系统设计是一个没有标准答案的 open-end 问题关键在于对于特定问题的设计选择俗称 trade-off。这也是较能考察面试者知识水平的一种题型。讲义给出了一份难度分布数据截至 2020-03-28以当时 LeetCode 设计标签的题量为基准后续会有增减仅作难度结构参考难度题量简单14 道中等32 道困难12 道合计58 道从仓库中各题题解的实现结构可以归纳出设计题的共性方法论最大频率栈题解中有这样一段概括非常适合作为解题总纲设计题目基本都是选择好数据结构那么算法实现就会很容易……你没有能做出来的原因很大程度上是因为对基础数据结构不熟悉。设计题基本不太会涉及到算法如果有算法也比较有限常见的有二分法。换言之设计题的解法几乎都是“选对数据结构 处理好边界与平局规则”。以下 6 道题正覆盖了这一套路的主要分支辅助栈模式、树形结构、双结构模拟、哈希 链表索引、指针伪状态等。二、题目列表六道精选设计题讲义精选了 6 道题进行详细讲解链接均指向本仓库problems/下的完整题解题目难度完整题解155. 最小栈Min Stack简单problems/155.min-stack.md211. 添加与搜索单词 - 数据结构设计中等problems/211.add-and-search-word-data-structure-design.md232. 用栈实现队列简单problems/232.implement-queue-using-stacks.md460. LFU 缓存困难problems/460.lfu-cache.md895. 最大频率栈困难problems/895.maximum-frequency-stack.md900. RLE 迭代器中等problems/900.rle-iterator.md下面逐题展开每题聚焦其核心 trade-off。三、155. 最小栈用辅助栈还是用值编码题目要求设计一个支持push、pop、top操作并能在常数时间内检索最小元素getMin的栈。前置知识是栈的基本概念。核心矛盾在于栈只有栈顶可访问而最小值可能藏在栈的任意深度要让getMin达到 O(1)就必须“预先付出代价”把最小值信息在 push/pop 时同步维护好。题解给出两种方案正好对应两种 trade-off。方案 A双栈辅助最小栈用一个正常数据栈承载全部元素另用一个minStack只保存“入栈时刻为止的最小值”class MinStack: def __init__(self): self.stack [] self.minstack [] def push(self, x: int) - None: self.stack.append(x) if not self.minstack or x self.minstack[-1]: self.minstack.append(x) def pop(self) - None: tmp self.stack.pop() if tmp self.minstack[-1]: self.minstack.pop() def top(self) - int: return self.stack[-1] def min(self) - int: return self.minstack[-1]来自 155.min-stack.md 的 Python3 实现。关键点push 到 minStack 的判断条件必须是x minStack 栈顶含相等。若用严格小于当最小值重复出现时pop 掉第一个最小值后 minStack 会错误地把已出栈的最小值留在栈顶pop 时只有出栈元素恰好等于 minStack 栈顶才同步弹出 minStack保证两栈的“水位”始终对应每个操作时间 O(1)辅助栈每个数据元素至多对应一个记录最坏入栈序列单调递减占用 O(n) 空间。方案 B单栈值编码差值法更省空间的思路是只维护一个栈 一个标量minV入栈时不存真实值而是存“真实值 − 当前最小值”的差同时用标量minV记录当前最小值。还原与更新规则如下push(x)先比较 x 与当前minV若 x 更小则更新minV x压入x − 更新前的 minV更新前pop / top 遇到差值 0说明栈顶就是历史最小值本身top 直接返回minVpop 时把minV回滚为minV − 差值即还原“上一个最小值”差值 ≥ 0top 返回差值 minVpop 不影响minV。class MinStack: def __init__(self): self.minV float(inf) self.stack [] def push(self, x: int) - None: self.stack.append(x - self.minV) if x self.minV: self.minV x def pop(self) - None: if not self.stack: return tmp self.stack.pop() if tmp 0: self.minV - tmp def top(self) - int: if not self.stack: return tmp self.stack[-1] if tmp 0: return self.minV return self.minV tmp def min(self) - int: return self.minV题解特别强调top 还原时加的是**“上一个”最小值而非“当前的最小值”**这正是差值法最易出错的地方。本题的 trade-off双栈逻辑直观、不易错代价是多一份最坏 O(n) 的辅助空间差值法只占 O(1) 额外空间但栈内不再是真实值top/pop 都需要一次还原运算且对负数边界差值为 0 恰好是最小值本身要求实现者格外小心。面试中一般先给出双栈方案保证正确性再主动提出差值法展示对空间极限的考量——这就是 trade-off 的体现。四、211. 添加与搜索单词用前缀树把通配符搜索降到 O(h)题目要求实现WordDictionaryaddWord(word)添加单词search(word)判断是否存在与 word 匹配的已添加单词其中.可代表任意单个字母。约束word.length 500addWord与search总调用次数最多 50000 次。从暴力到前缀树的演进题解的思路演进很典型见 211.add-and-search-word-data-structure-design.md朴素方案数组追加 线性查找。遇到.视为匹配任意字母继续往后比。实现最简但每次 search 是 O(n·m)n 为单词数m 为词长50000 次调用下不可接受前缀树优化把单词插入 Trieinsert与标准前缀树完全一致只需改造search遇到.时对当前节点的所有子分支做一次 DFS 分支搜索。优化后单次查找复杂度为O(h)h 为前缀树深度即最长单词长度。def search(self, word): Returns if the word is in the trie. word 中的 . 匹配任意字母 curr self.Trie for i, w in enumerate(word): if w .: wizards [] for k in curr.keys(): if k #: continue wizards.append(self.search(word[:i] k word[i 1:])) return any(wizards) if w not in curr: return False curr curr[w] return # in curr对比标准无通配符前缀树搜索差异只在w .分支——标准版本是逐字符沿唯一路径下探最后判断# in curr。Trie 本体insert与词尾标记#可以直接作为前缀树题解模板复用class Trie: def __init__(self): self.Trie {} def insert(self, word): curr self.Trie for w in word: if w not in curr: curr[w] {} curr curr[w] curr[#] 1本题的 trade-off空间换时间Trie 用节点数组空间把“前缀共享”显式化把线性扫描压缩成沿路径下探通配符的代价.分支最坏要展开 26 个子分支若单词中全是.单次 search 退化为 O(26^k)k 为.的个数——这是结构优化无法消除的下界也是面试中值得主动点出的边界。Trie 的系统讲解见 thinkings/trie.md。五、232. 用栈实现队列顺序反转与双栈分工题目要求仅使用标准栈操作实现push入队尾、pop出队首、peek、empty。为什么一个栈不够两个栈就够了题解232.implement-queue-using-stacks.md从过程演示切入向栈依次压入1, 2, 3, 4后队首元素 1 被压在栈底无法直接访问。若强行弹出 2/3/4 去够 1这三个元素就丢失了——正确做法是把它们转移到另一个辅助栈中保存。两个栈配合本质是利用“栈的反转性质”恢复 FIFO 顺序。题解给出了两种落点分别对应 push 时倒腾与 pop 时倒腾class MyQueue: def __init__(self): self.stack [] self.help_stack [] def push(self, x: int) - None: while self.stack: self.help_stack.append(self.stack.pop()) self.help_stack.append(x) while self.help_stack: self.stack.append(self.help_stack.pop()) def pop(self) - int: return self.stack.pop() def peek(self) - int: return self.stack[-1] def empty(self) - bool: return not bool(self.stack)此版本每次push都把元素在主栈与辅助栈之间完整倒腾一轮保持主栈“栈底 队首”的不变量因此pop/peek是 O(1)但push最坏 O(n)。仓库中的 Java 版本则把倒腾动作放在pop/peek一侧push直接进pushStack首次需要出队时才把pushStack全部搬到popStack。从该实现结构可以推断若把“倒腾”延迟到 pop 侧且只在popStack为空时发生则单次操作仍可能 O(n)但摊还到每次操作为 O(1)——每个元素一生最多被倒腾两次。题解给出的复杂度与延伸时间复杂度O(N)N 为栈中元素个数每次倒腾一次按题解所采用的“push 时倒腾”实现计空间复杂度O(N)辅助栈与主栈同规模。现实世界的双栈队列题解特别指出工程中用两个栈实现队列是为了在多线程场景下分开读写——读栈与写栈独立加锁只要写栈非空push的锁就不会阻塞pop单队列实现则读写都要锁整个队列。这是这道“玩具题”背后真实的并发价值。延伸用队列实现栈思路完全对称栈混洗shuffle也借助第二个栈完成两者结构相似。六、460. LFU 缓存两个 HashMap 按频率分组的双链表题目要求实现 LFULeast Frequently Used缓存get(key)命中返回正数否则 -1put(key, value)在容量满时淘汰使用频率最低的项频率相同则淘汰最久未使用的项。进阶要求两项操作均 O(1)。使用次数的定义是自插入以来get与put调用次数之和被移除后清零。数据结构设计题解460.lfu-cache.md给出的方案由三部分组成nodeMap: {key - node{key, val, freq}}键到节点的正向索引保证 get/put 定位 O(1)freqMap: {freq - 双链表}同一频率的所有节点挂进同一条带头尾哨兵的双链表链表内按“最近使用”排序新访问的插到 head 后淘汰取 tail 前一个标量minFreq记录当前最小频率淘汰时直接查freqMap[minFreq]的链表尾部无需全局比较。以题面示例capacity 2走一遍状态变迁put(1,1)新建 node1(1,1,freq1) 入 nodeMapfreq1 的链表新建后插入 node1put(2,2)node2 同样挂在 freq1 链表get(1)node1 频率 1从 freq1 链表移到 freq2 链表minFreq仍为 1put(3,3)容量已满淘汰minFreq1链表的尾节点 node2即 key 2再插入 node3(freq1)minFreq重置为 1get(2)→ -1get(3)node3 升到 freq2put(4,4)再淘汰 freq1 链表尾部的 node1key 1插入 node4get(1)→ -1get(3)node3 升到 freq3get(4)node4 升到 freq2。核心更新逻辑update(node)做了三件事从旧频率链表摘除节点若旧链表为空且 node.freq minFreq则 minFreqfreq1 后挂入新频率链表头部。minFreq只在“被淘汰侧的链表清空”时才递增这是保证 O(1) 的关键不变量。private void update(Node node) { DoubleLinkedList oldList freqMap.get(node.freq); oldList.remove(node); if (node.freq minFreq oldList.size 0) minFreq; node.freq; DoubleLinkedList newList freqMap.getOrDefault(node.freq, new DoubleLinkedList()); newList.add(node); freqMap.put(node.freq, newList); } public int get(int key) { Node node nodeMap.get(key); if (node null) return -1; update(node); return node.val; } public void put(int key, int value) { if (capacity 0) return; Node node; if (nodeMap.containsKey(key)) { node nodeMap.get(key); node.val value; update(node); } else { node new Node(key, value); nodeMap.put(key, node); if (nodeMap.size() capacity) { DoubleLinkedList lastList freqMap.get(minFreq); nodeMap.remove(lastList.removeLast().key); } minFreq 1; DoubleLinkedList newList freqMap.getOrDefault(node.freq, new DoubleLinkedList()); newList.add(node); freqMap.put(node.freq, newList); } }节选自 460.lfu-cache.md 的完整 Java 实现含Node与DoubleLinkedList定义完整代码请见原文件。本题的 trade-off平局规则决定结构LFU 的“同频淘汰最久未用”要求同一频率内保留 LRU 顺序这正是每条频率链表要维护插入序的原因若规则改成“同频任意淘汰”用 HashSet 即可链表可省minFreq 的 O(1) 维护不用每步全量扫描求最小频率而是依赖“最小频率只会从 1 递增或在新节点插入时归 1”这一性质题解还提示用 Java 自带LinkedHashSet等容器替代手写 Node/双链表可显著缩减代码量属于“正确性优先、代码量其次”的实用 trade-off。链表与哈希表的背景可参考 thinkings/linked-list.md。七、895. 最大频率栈按频率分组的栈 最大频率水位题目要求实现FreqStackpush(x)压栈pop()弹出出现频率最高的元素频率并列时弹出最接近栈顶者。调用规模push/pop 各最多 10000 次/例全体样例总调用 150000 次。结构设计的巧妙之处题解895.maximum-frequency-stack.md指出弹出“频率最高且最靠栈顶”需要三个信息协同freq: {x - 次数}统计每个数字的出现频率数字范围到 10^9必须用哈希表max_freq当前全局最大频率pop 时直接定位目标组freq_stack: {频率 - 数字组成的栈}每个频率组都是一个栈组内后入先出天然满足“最接近栈顶”的平局规则。最容易被忽略的设计点在于freq_stack[f]保存的是所有出现次数 ≥ f 的数字且数字 x 会随每次 push 被追加进freq_stack[1..当前次数]的多个组。题解称这是“故意的”当 x 从频率 3 弹出回频率 2 时它在freq_stack[2]中的位置早在第二次 push 时就已就位pop 无需重插入、无需定位只需从freq_stack[max_freq]顶部取走即可。以题面示例push 序列 5,7,5,7,4,5走一遍push 后栈自底向上: [5,7,5,7,4,5] freq {5:3, 7:2, 4:1} freq_stack {1:[5,7,4], 2:[7,5], 3:[5]} max_freq 3 pop() - 5频率 3 唯一 pop() - 75 与 7 并列频率 27 更靠栈顶 pop() - 5 pop() - 4class FreqStack: def __init__(self): self.fraq collections.defaultdict(lambda: 0) self.fraq_stack collections.defaultdict(list) self.max_fraq 0 def push(self, x: int) - None: self.fraq[x] 1 if self.fraq[x] self.max_fraq: self.max_fraq self.fraq[x] self.fraq_stack[self.fraq[x]].append(x) def pop(self) - int: ans self.fraq_stack[self.max_fraq].pop() self.fraq[ans] - 1 if not self.fraq_stack[self.max_fraq]: self.max_fraq - 1 return anspush 时更新三处状态freq、max_freq、freq_stackpop 时同步回收当freq_stack[max_freq]弹空时max_freq恰好减 1因为任何小于 max_freq 的组都不可能为空若为空其组内数字的频率都低于 max_freq与 max_freq 的定义矛盾。均摊时间 O(1)空间随 push 总量线性增长。本题的 trade-off空间冗余换定位能力同一数字在多个频率组中重复存放用 O(push 总次数) 的空间冗余把“弹出后回迁”这个最难的正确性问题彻底消解与 LFU 对比两者都是“哈希统计 分组结构”但 LFU 的平局规则LRU需要链表维护顺序而 895 的平局规则LIFO用栈即可平局规则直接决定了分组容器选型——这是两道题放在一起读最大的收获。八、900. RLE 迭代器原地修改还是指针伪更新背景游程编码RLE游程编码讲义给出定义RLE 将连续重复的字符编码为次数, 字符对例如AAAAABBBBCCC编码为5A4B3C。它与 Huffman 编码一样是无损压缩几乎所有常见无损格式PNG、GIF、ZIP 等都组合使用二者。本题正是 RLE 的迭代消费场景。题目要求RLEIterator(A)以偶数长度数组 A 初始化其中A[2k]表示A[2k1]连续出现的次数例如A [3,8,0,9,2,5]对应序列[8,8,8,5,5]。next(n)耗尽接下来 n 个元素并返回最后一个被耗尽的元素剩余元素不足时返回 -1。约束A.length 1000且为偶数A[i]与n可达 10^9next每例最多调用 1000 次。注意 10^9 的量级把序列展开成真实数组在空间上不可行必须直接在 RLE 编码上迭代。两种实现取向题解900.rle-iterator.md指出算法分初始化与next(n)两部分核心循环是判断 n 是否大于 A[i]i 从 0 开始。如果大于说明不够移除数组前两项更新 n重复判断如果小于说明够了更新 A[i]。但“移除前两项 / 更新 A[i]”是原地修改思路——它破坏了原始编码。题解给出的自己的解法采用伪更新用一个current指针记录当前访问到的编码位置只扣减计数不改结构便于保留原始数据var RLEIterator function(A) { this.A A; this.current 0; }; /** param {number} n return {number} */ RLEIterator.prototype.next function(n) { const A this.A; while(this.current A.length A[this.current] n){ n n - A[this.current]; this.current 2; } if(this.current A.length){ return -1; } A[this.current] A[this.current] - n; // 更新 Count return A[this.current 1]; // 返回 element };逻辑与题面示例对得上next(2)耗尽 2 个 8 返回 8next(1)耗尽最后一个 8next(1)跨过计数为 0 的 9返回 5next(2)只够耗尽 1 个 5 后序列见底返回 -1。本题的 trade-off原地修改 vs 伪更新原地改A最省空间但编码不可复用、不可重放指针方案多一个current变量即可在保留原始数据的前提下实现同样的推进逻辑代价是最终仍会扣减当前组的计数题解的实现属于“混合”跳过组不动、当前组扣减。若要求严格不可变可再引入“已消耗量”变量为什么必须迭代而不展开n达 10^9 而编码长度仅 1000O(编码段数) 的推进是唯一可行的复杂度。九、设计题套路总结从六道题目提炼的 Trade-off 决策表题目核心矛盾选型的 trade-off平局/边界规则155 最小栈最小值藏在栈深处getMin 要 O(1)辅助栈直观、最坏 O(n) 空间 vs 差值编码O(1) 额外空间、实现易错相等值必须同步入 minStack用211 单词词典线性扫描扛不住 5 万次调用数组暴力 vs Trie空间换时间O(h) 查找.分支 DFS最坏 O(26^k)232 双栈队列栈的 LIFO 与队列的 FIFO 冲突单栈不可行双栈倒腾顺序push 时 vs pop 时决定复杂度落点工程意义读写栈分离以降低锁粒度460 LFU 缓存淘汰低频 同频淘汰最旧还要 O(1)两个 HashMap 按频率分组双链表 minFreq 水位同频 LRU 顺序由链表插入序保证895 最大频率栈弹最高频 同频最靠顶频率组内用栈LIFO 天然满足平局数字在多组冗余存放freq_stack[f] 含所有频率 ≥ f 的元素900 RLE 迭代器10^9 量级下不能展开序列原地改编码 vs current 指针伪更新计数为 0 的组直接跨过三条可复用的经验全部来自上述题解的共同模式先锁定 API 的复杂度目标再反推结构getMin/next 要 O(1)就必须在状态量辅助栈、minFreq、freq_stack、current上预付空间平局tie-break规则决定辅助容器LIFO 规则 → 栈LRU 规则 → 有序链表无顺序要求 → 哈希集合即可状态更新点要集中LFU 的update(node)、895 的 push/pop 三处同步都是把“容易漏掉的不变量维护”收敛到单一函数正确性随之可论证。十、相关延伸阅读本仓库中与本文主题直接相关的进一步材料设计题中文讲义thinkings/design.md本文英文原稿对应 thinkings/design.en.md前缀树系统讲义thinkings/trie.md游程编码与哈夫曼编码thinkings/run-length-encode-and-huffman-encode.md基础数据结构栈/队列thinkings/basic-data-structure.md链表thinkings/linked-list.md六道题的完整题解多语言实现、逐步图解problems/155.min-stack.md、problems/211.add-and-search-word-data-structure-design.md、problems/232.implement-queue-using-stacks.md、problems/460.lfu-cache.md、problems/895.maximum-frequency-stack.md、problems/900.rle-iterator.md【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考