LeetCode 最大栈题解题目描述设计一个支持pushpoptoppeekMax和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]总结最大栈是一个经典的栈问题它可以通过双栈来高效地解决。双栈法的核心思想是使用一个主栈存储所有元素一个辅助栈存储最大值确保在常数时间内可以获取到最大值。掌握双栈法对于解决类似的问题非常重要。