❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！
- 推荐：数据分析螺丝钉的首页
- 导航：
- LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
- 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
- python源码解读：解读python的源代码与调用关系，快速提升代码质量
- python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
- 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识
期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️
在本篇文章中，我们将详细解读力扣第155题“最小栈”。通过学习本篇文章，读者将掌握如何设计一个支持常数时间复杂度检索最小元素的栈。我们将介绍多种解决方案，详细分析它们的优缺点，并提供相应的代码实现。每种方法都将配以详细的解释和图示，以便于理解。
问题描述
力扣第155题“最小栈”描述如下：
设计一个支持
push、pop、top操作，并能在常数时间内检索到最小元素的栈。
push(x)– 将元素 x 推入栈中。pop()– 删除栈顶的元素。top()– 获取栈顶元素。getMin()– 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
解题思路
- 初步分析：
- 我们需要设计一个栈，支持常见的栈操作（
push、pop、top）和一个额外的操作（getMin）。 - 关键在于如何在常数时间内实现
getMin操作。
- 多种解法：
- 使用辅助栈法：利用两个栈，一个存储数据，一个存储最小值。
- 使用栈中元素存储最小值法：在栈中每个元素同时存储当前元素和栈内最小值。
辅助栈法
解法思路
使用两个栈，一个栈 dataStack 用于存储所有的元素，另一个栈 minStack 用于存储当前最小值。
步骤
- push(x)：
- 将
x压入dataStack。 - 如果
minStack为空或者x小于等于minStack的栈顶元素，则将x压入minStack。
- pop()：
- 从
dataStack弹出栈顶元素。 - 如果
dataStack弹出的元素等于minStack的栈顶元素，则从minStack也弹出栈顶元素。
- top()：
- 返回
dataStack的栈顶元素。
- getMin()：
- 返回
minStack的栈顶元素。
代码实现
class MinStack: def __init__(self): self.dataStack = [] self.minStack = [] def push(self, x: int) -> None: self.dataStack.append(x) if not self.minStack or x <= self.minStack[-1]: self.minStack.append(x) def pop(self) -> None: if self.dataStack: top = self.dataStack.pop() if top == self.minStack[-1]: self.minStack.pop() def top(self) -> int: return self.dataStack[-1] if self.dataStack else None def getMin(self) -> int: return self.minStack[-1] if self.minStack else None # 测试案例 minStack = MinStack() minStack.push(-2) minStack.push(0) minStack.push(-3) print(minStack.getMin()) # --> 返回 -3. minStack.pop() print(minStack.top()) # --> 返回 0. print(minStack.getMin()) # --> 返回 -2.
图解
操作: push(-2) dataStack: [-2] minStack: [-2] 操作: push(0) dataStack: [-2, 0] minStack: [-2] 操作: push(-3) dataStack: [-2, 0, -3] minStack: [-2, -3] 操作: getMin() 返回: -3 操作: pop() dataStack: [-2, 0] minStack: [-2] 操作: top() 返回: 0 操作: getMin() 返回: -2
使用栈中元素存储最小值法
解法思路
在栈中每个元素同时存储当前元素和栈内最小值。
步骤
- push(x)：
- 如果栈为空，则将
(x, x)压入栈，表示当前元素和当前最小值都是x。 - 否则，将
(x, min(x, 当前最小值))压入栈。
- pop()：
- 从栈中弹出栈顶元素。
- top()：
- 返回栈顶元素的第一个值。
- getMin()：
- 返回栈顶元素的第二个值。
代码实现
class MinStack: def __init__(self): self.stack = [] def push(self, x: int) -> None: if not self.stack: self.stack.append((x, x)) else: current_min = self.stack[-1][1] self.stack.append((x, min(x, current_min))) def pop(self) -> None: if self.stack: self.stack.pop() def top(self) -> int: return self.stack[-1][0] if self.stack else None def getMin(self) -> int: return self.stack[-1][1] if self.stack else None # 测试案例 minStack = MinStack() minStack.push(-2) minStack.push(0) minStack.push(-3) print(minStack.getMin()) # --> 返回 -3. minStack.pop() print(minStack.top()) # --> 返回 0. print(minStack.getMin()) # --> 返回 -2.
图解
操作: push(-2) stack: [(-2, -2)] 操作: push(0) stack: [(-2, -2), (0, -2)] 操作: push(-3) stack: [(-2, -2), (0, -2), (-3, -3)] 操作: getMin() 返回: -3 操作: pop() stack: [(-2, -2), (0, -2)] 操作: top() 返回: 0 操作: getMin() 返回: -2
复杂度分析
- 辅助栈法：
- 时间复杂度：
push操作：O(1)pop操作：O(1)top操作：O(1)getMin操作：O(1)
- 空间复杂度：O(N)，其中 N 是栈中元素的数量。需要额外的栈来存储最小值。
- 使用栈中元素存储最小值法：
- 时间复杂度：
push操作：O(1)pop操作：O(1)top操作：O(1)getMin操作：O(1)
- 空间复杂度：O(N)，其中 N 是栈中元素的数量。栈中的每个元素存储两个值。
测试案例分析
- 测试案例 1：
- 操作：
push(-2),push(0),push(-3),getMin(),pop(),top(),getMin() - 输出：
-3,0,-2 - 解释：通过连续的栈操作，可以验证
getMin方法能够正确返回最小值。
- 测试案例 2：
- 操作：
push(2),push(2),push(1),getMin(),pop(),getMin(),pop(),getMin() - 输出：
1,2,2 - 解释：通过重复的元素和变化的最小值，验证栈操作的正确性。
总结
本文详细解读了力扣第155题“最小栈”，通过辅助栈法和使用栈中元素存储最小值法两种不同的解法，帮助读者深入理解如何高效地实现一个支持常数时间内获取最小值的栈。希望读者通过本文的学习，能够在力扣刷题的过程中更加得心应手。
参考资料
- 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- 力扣官方题解
🌹🌹如果觉得这篇文对你有帮助的话，记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励，非常感谢 ❥(^_-)
❤️❤️关注公众号 数据分析螺丝钉 回复 学习资料 领取高价值免费学习资料❥(^_-)
欢迎关注微信公众号 数据分析螺丝钉
