LeetCode 155. 最小栈一、它要实现什么1. 栈和 Python 的 list 原来不是一回事2. 测试样例里的 push、pop 是字符串我还要自己判断吗3. 那 getMin() 怎么知道前面 push、pop 过什么二、我最开始想直接排序找最小值三、那干脆一直保存当前最小值四、用 min_stack 保存以前出现过的最小值push() 时怎么维护pop() 时怎么维护五、最终代码为什么一定要 不能只写 简单走一遍六、复杂度七、最后复盘题目链接155. 最小栈弄了个网站, 可以看代码是怎么操作达到最终要的结果: 过程可视化题目要求我们实现一个MinStack支持push(value)加入一个元素pop()删除栈顶元素top()查看栈顶元素getMin()得到当前栈里的最小值而且这些操作都要求在O(1)的时间内完成。如果你觉得这篇有帮你捋清了思路可以点个赞支持我一下吗?让我有动力继续写更多 LeetCode 题解 ~一、它要实现什么1. 栈和 Python 的list原来不是一回事我看到题目让我实现push()、pop()、top()第一反应是难道连栈本身都要我从头实现不能直接用 Python 的list、append()、pop()吗后来才捋清楚栈是一种数据结构也可以理解成一种使用规则list是 Python 提供的具体容器我们可以用list去模拟栈栈规定的是后进先出LIFO而且主要操作栈顶。Python 的list本身其实比栈自由得多例如可以nums[0]nums[3]nums.insert(...)访问、修改任意位置。但如果我们主动只使用stack.append(value)# pushstack.pop()# popstack[-1]# top相当于限制自己只从一端操作 list这样它就表现成了一个栈。所以这道题是让我利用list实现MinStack需要的这些功能。2. 测试样例里的push、pop是字符串我还要自己判断吗LeetCode 的输入看起来可能类似[MinStack, push, push, pop, getMin]我当时就在想这些不是字符串吗难道我要自己遍历然后看到push就调用 push看到pop就调用 pop其实不用。LeetCode 会帮我们调用对应的方法。它背后相当于在做objMinStack()obj.push(5)obj.push(3)obj.pop()obj.getMin()我们只需要把每个方法分别实现好。3. 那getMin()怎么知道前面 push、pop 过什么这个是我当时最疑惑的地方。比如之前已经执行push → push → pop → getMin那getMin()怎么知道前面发生了什么我一开始甚至想过难道getMin()还得回头遍历前面的操作记录后来才明白不需要。关键是self。def__init__(self):self.stack[]这里的self.stack属于当前这个MinStack对象。同一个实例对象里的所有方法都可以通过self访问和修改同一份实例数据。例如push(5) → self.stack [5] push(3) → self.stack [5, 3] pop() → self.stack [5] top() → 看到的还是这一个 self.stack所以不是每调用一个函数就重新创建一次数据。如果另外创建obj1MinStack()obj2MinStack()那么obj1.stack和obj2.stack又是两份独立的数据互不影响。二、我最开始想直接排序找最小值普通的push()、pop()、top()其实很快就能写出来。可以看这个学习一下: 使用 Python 实现一个简单的栈Stack类 | 菜鸟教程记住, 不要漏掉self去调用stack对象真正麻烦的是getMin()我第一反应很直接那我把栈排序一下然后返回第一个不就是最小值了吗例如new_stacksorted(self.stack)returnnew_stack[0]这样确实能找到最小值。不过这里我还踩到了一个 Python 的小坑。如果写new_stackself.stack这不是复制一份新的列表。它只是给同一个 list 又起了一个名字new_stack ─┐ ├→ 同一个列表 self.stack ┘所以修改new_stackself.stack也会跟着变化。真正复制可以写new_stackself.stack.copy()或者直接new_stacksorted(self.stack)不过即使复制以后再排序这个思路还是不能用。因为排序需要O(n log n)而题目要求getMin() → O(1)所以问题变成了不能等到调用getMin()的时候再重新计算最小值。三、那干脆一直保存当前最小值既然每次重新找最小值太慢我接着想到那我额外存一个min_value专门记录现在的最小值不就好了比如push(5)→min_value 5push(3)→3 5所以min_value 3push(7)→min_value还是3对于push()来说这个思路很好处理。每次新加入一个值只需要新 value vs 当前 min_value → 谁小就保存谁但问题马上出现在pop()。例如stack [5, 3, 7, 2] min_value 2现在pop()→ 把2删除了。普通栈变成[5, 3, 7]新的最小值应该重新变成3但此时单独的min_value 2已经失效了。而我们没有任何地方记录上一个最小值其实是3。如果这时候重新遍历整个栈寻找最小值又会变成O(n)。所以这里真正的问题就出来了不能只保存“现在的最小值”还得保留“以前出现过的最小值”。→ 那这些以前的最小值要怎么保存这里会想到栈是因为我们恢复最小值的顺序刚好也是后进先出。比如最小值依次变化5 → 3 → 2那么2是最新的最小值。如果它被 pop 掉我们下一步需要恢复的不是5而是刚刚被它替代的35 ↓ 3 ↓ 2 ← 当前最小值 pop 2 ↓ 重新回到 3也就是说最新出现的最小值最先失效失效以后要恢复它前一个最小值。这正好符合栈的后进先出LIFO所以可以再准备一个栈self.min_stack[]专门记录这些最小值的变化。当然Python 底层依然可以用list来保存它这里说它是min_stack强调的是我们会按照栈的方式只操作最后加入的那个最小值。四、用min_stack保存以前出现过的最小值初始化的时候准备两个栈def__init__(self):self.stack[]self.min_stack[]它们分别负责stack→ 保存所有正常元素min_stack→ 保存当前以及以前出现过的最小值这里最关键的一点是不是等到getMin()被调用的时候再去找最小值而是在每次push()、pop()的时候就顺便把min_stack维护好。这样以后getMin()只需要returnself.min_stack[-1]就好了。 题目还特别说明pop、top和getMin操作总是在非空栈上调用。所以在这三个方法里我们可以直接访问self.stack[-1]self.min_stack[-1]不用再额外判断栈是否为空。push()时怎么维护假设现在min_stack [5, 3]说明当前最小值是3如果push(7)因为7 3它不会成为新的最小值所以不需要进入min_stack。但如果push(2)因为2 3新的最小值变成了2所以self.min_stack.append(2)也就是说ifnotself.min_stackorvalueself.min_stack[-1]:self.min_stack.append(value)这里的notself.min_stack负责处理第一次push()。min_stack 为空 → 当前 value 就是第一个最小值 → 直接记录进去而 因为前面说了操作总是在非空栈上调用。所以后半部分直接进行对比不用再额外判断栈是否为空。 注意我这里的min_stack不需要和普通栈长度一样。例如stack [5, 3, 7, 2] min_stack [5, 3, 2]7根本不需要进去。只要保证min_stack[-1]始终是当前普通栈中的最小值就可以。pop()时怎么维护还是stack [5, 3, 7, 2] min_stack [5, 3, 2]现在如果pop()删除的是2而2 min_stack[-1]说明被删除的正好是当前最小值。所以min_stack也要self.min_stack.pop()变成min_stack [5, 3]于是新的min_stack[-1]自然就是3但如果普通栈删除的是7因为7 ! min_stack[-1]说明这个元素根本没有影响最小值。那么min_stack不需要动。所以整个关系其实就是push / pop → 每次顺便维护 min_stack getMin → 不重新计算 → 直接读取 min_stack[-1]五、最终代码classMinStack:def__init__(self):self.stack[]self.min_stack[]defpush(self,value:int)-None:self.stack.append(value)ifnotself.min_stackorvalueself.min_stack[-1]:self.min_stack.append(value)defpop(self)-None:valueself.stack.pop()ifvalueself.min_stack[-1]:self.min_stack.pop()deftop(self)-int:returnself.stack[-1]defgetMin(self)-int:returnself.min_stack[-1]为什么一定要不能只写这个地方也很容易漏。例如push(2) push(2)如果条件只写valueself.min_stack[-1]那么第二个2因为没有更小就不会进入min_stack。结果stack [2, 2] min_stack [2]现在 pop 一个2。因为被删除的是当前最小值所以min_stack也把唯一的2删除。变成stack [2] min_stack []但普通栈里明明还有一个2。这时候getMin()就出问题了。所以相同的最小值也必须记录valueself.min_stack[-1]这样push(2) push(2) stack [2, 2] min_stack [2, 2]pop 一次以后stack [2] min_stack [2]最小值仍然正确。简单走一遍依次push(5) → push(3) → push(7) → push(2)得到stack [5, 3, 7, 2] min_stack [5, 3, 2]此时getMin()→2执行pop()删除2stack [5, 3, 7] min_stack [5, 3]再次getMin()→3再 pop 掉7stack [5, 3] min_stack [5, 3]因为7本来就不是当前最小值所以min_stack不需要发生变化。题目本身保证调用pop()、top()、getMin()时栈非空所以这里不用额外处理空栈调用。六、复杂度四个操作都已经满足题目要求push()O(1)pop()O(1)top()O(1)getMin()O(1)整个数据结构的空间复杂度是O(n)因为普通的self.stack本身就要保存所有压入的元素。如果只看辅助的min_stack元素一直递增例如1, 2, 3, 4它可能只保存一个最小值元素一直递减例如5, 4, 3, 2, 1每个元素都会成为新的最小值min_stack最坏也会达到 O(n)。但整个MinStack最终还是O(n)七、最后复盘这道题我的思路变化大概是先搞懂 栈不是 list 而是可以用 list 实现的一种操作规则 ↓ 再搞懂 LeetCode 会自动调用 push / pop / getMin 不需要自己解析测试字符串 ↓ 最开始想 getMin → 排序 → 拿第一个 ↓ 发现 排序不是 O(1) ↓ 那就专门存一个 min_value ↓ push 很容易更新 但是当前最小值一旦被 pop 上一个最小值是谁 ↓ 说明 只记一个 min_value 不够 ↓ 增加 min_stack 保存以前出现过的最小值 ↓ push / pop 时同步维护它 ↓ getMin 不需要重新计算 直接返回 min_stack[-1] ↓ 四个操作全部做到 O(1)这道题我觉得真正值得记住的是如果某个查询要求非常快可以考虑不要等到“查询的时候”再重新计算而是在数据发生变化的时候就提前把需要的信息维护好。这里就是push / pop 时维护最小值 → getMin 时直接读取。