LeetCode 155. Min Stack 题解
题目描述
设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。
实现MinStack类：
MinStack()初始化堆栈对象。void push(int val)将元素 val 推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
示例 1：
输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2] 解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.解题思路
方法：辅助栈
思路：
- 使用两个栈，一个主栈用于存储所有元素，一个辅助栈用于存储当前的最小元素
- 当推入元素时，将元素压入主栈，并将当前最小元素压入辅助栈
- 当弹出元素时，同时弹出主栈和辅助栈的栈顶元素
- 当获取顶部元素时，返回主栈的栈顶元素
- 当获取最小元素时，返回辅助栈的栈顶元素
复杂度分析：
- 时间复杂度：O(1)，所有操作都是常数时间。
- 空间复杂度：O(n)，需要使用两个栈来存储元素。
代码实现
方法：辅助栈
class MinStack: def __init__(self): # 初始化主栈和辅助栈 self.stack = [] self.min_stack = [] def push(self, val: int) -> None: # 将元素压入主栈 self.stack.append(val) # 将当前最小元素压入辅助栈 # 如果辅助栈为空，或者当前元素小于等于辅助栈的栈顶元素，则压入 if not self.min_stack or val <= self.min_stack[-1]: self.min_stack.append(val) # 否则，再次压入辅助栈的栈顶元素 else: self.min_stack.append(self.min_stack[-1]) def pop(self) -> None: # 同时弹出主栈和辅助栈的栈顶元素 if self.stack: self.stack.pop() self.min_stack.pop() def top(self) -> int: # 返回主栈的栈顶元素 if self.stack: return self.stack[-1] return None def getMin(self) -> int: # 返回辅助栈的栈顶元素 if self.min_stack: return self.min_stack[-1] return None测试用例
测试用例 1：
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]输出：
[null,null,null,null,-3,null,0,-2]总结
本题是栈的经典应用问题，主要考察对栈数据结构的理解和使用。通过使用辅助栈，我们可以在常数时间内检索到最小元素。
辅助栈的核心思想是：使用两个栈，一个主栈用于存储所有元素，一个辅助栈用于存储当前的最小元素，当推入元素时，将当前最小元素压入辅助栈，当弹出元素时，同时弹出主栈和辅助栈的栈顶元素。
这种方法不仅适用于最小栈问题，还可以应用于许多其他需要在常数时间内检索到特定元素的问题。掌握辅助栈的使用，对于解决这类问题非常重要。
