LeetCode 155. Min Stack 题解

LeetCode 155. Min Stack 题解题目描述设计一个支持pushpoptop操作并能在常数时间内检索到最小元素的栈。实现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]总结本题是栈的经典应用问题主要考察对栈数据结构的理解和使用。通过使用辅助栈我们可以在常数时间内检索到最小元素。辅助栈的核心思想是使用两个栈一个主栈用于存储所有元素一个辅助栈用于存储当前的最小元素当推入元素时将当前最小元素压入辅助栈当弹出元素时同时弹出主栈和辅助栈的栈顶元素。这种方法不仅适用于最小栈问题还可以应用于许多其他需要在常数时间内检索到特定元素的问题。掌握辅助栈的使用对于解决这类问题非常重要。