LeetCode 最大栈题解
LeetCode 最大栈题解
题目描述
设计一个支持push，pop，top，peekMax和popMax操作的栈。
示例：
输入：
["MaxStack","push","push","push","top","popMax","top","peekMax","pop","top"] [[],[5],[1],[5],[],[],[],[],[],[]]输出：[null,null,null,null,5,5,1,5,1,5]
解题思路
方法：双栈
思路：
- 使用两个栈来实现最大栈：一个主栈（stack）用于存储所有元素，一个辅助栈（max_stack）用于存储最大值。
- 当调用 push 操作时，将元素压入主栈，如果辅助栈为空或当前元素大于等于辅助栈的栈顶元素，将当前元素压入辅助栈，否则将辅助栈的栈顶元素再次压入辅助栈。
- 当调用 pop 操作时，同时弹出主栈和辅助栈的栈顶元素。
- 当调用 top 操作时，返回主栈的栈顶元素。
- 当调用 peekMax 操作时，返回辅助栈的栈顶元素。
- 当调用 popMax 操作时，需要特殊处理：弹出辅助栈的栈顶元素，然后使用一个临时栈来保存主栈中弹出的元素，直到找到与辅助栈栈顶元素相等的元素，弹出该元素，然后将临时栈中的元素重新压入主栈和辅助栈。
复杂度分析：
- 时间复杂度：push、pop、top、peekMax 操作的时间复杂度是 O(1)，popMax 操作的时间复杂度是 O(n)。
- 空间复杂度：O(n)，需要额外的空间来存储元素。
代码实现
方法：双栈
# 最大栈（双栈） class MaxStack: def __init__(self): self.stack = [] self.max_stack = [] def push(self, x): self.stack.append(x) # 如果辅助栈为空或当前元素大于等于辅助栈的栈顶元素，压入当前元素 if not self.max_stack or x >= self.max_stack[-1]: self.max_stack.append(x) else: # 否则将辅助栈的栈顶元素再次压入辅助栈 self.max_stack.append(self.max_stack[-1]) def pop(self): if self.stack: self.max_stack.pop() return self.stack.pop() def top(self): if self.stack: return self.stack[-1] def peek_max(self): if self.max_stack: return self.max_stack[-1] def pop_max(self): if not self.stack: return None max_val = self.max_stack[-1] temp = [] # 将主栈中大于 max_val 的元素弹出并保存到临时栈 while self.stack and self.stack[-1] != max_val: temp.append(self.stack.pop()) self.max_stack.pop() # 弹出 max_val self.stack.pop() self.max_stack.pop() # 将临时栈中的元素重新压入主栈和辅助栈 while temp: val = temp.pop() self.stack.append(val) if not self.max_stack or val >= self.max_stack[-1]: self.max_stack.append(val) else: self.max_stack.append(self.max_stack[-1]) return max_val # 测试 def test_max_stack(): obj = MaxStack() obj.push(5) obj.push(1) obj.push(5) print(obj.top()) # 输出：5 print(obj.pop_max()) # 输出：5 print(obj.top()) # 输出：1 print(obj.peek_max()) # 输出：5 print(obj.pop()) # 输出：1 print(obj.top()) # 输出：5 if __name__ == "__main__": test_max_stack()测试用例
测试用例 1：基本情况
输入：
["MaxStack","push","push","push","top","popMax","top","peekMax","pop","top"] [[],[5],[1],[5],[],[],[],[],[],[]]输出：[null,null,null,null,5,5,1,5,1,5]
总结
最大栈是一个经典的栈问题，它可以通过双栈来高效地解决。
双栈法的核心思想是：使用一个主栈存储所有元素，一个辅助栈存储最大值，确保在常数时间内可以获取到最大值。
掌握双栈法，对于解决类似的问题非常重要。