设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) —— 将元素 x 推入栈中。 - pop() —— 删除栈顶的元素。 - top() —— 获取栈顶元素。 - getMin() —— 检索栈中的最小元素。
注：leetcode所有相关代码均在leetcode平台中通过
输入： [“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.
class MinStack: # 为了使在常数时间内检索到最小元素的栈，一般都是时间换空间或者空间换时间 # 所以这里空间换时间，stack中保存数据+当前栈中的最小值 def __init__(self): """ initialize your data structure here. """ self.stack = []; def push(self, x: int) -> None: current_min = self.getMin(); # 特别注意 这里的数值为0与下面的none有bug 不能写成not current_min 因为0也满足条件 if (current_min==None) or x < current_min: current_min = x; self.stack.append((x, current_min)); def pop(self) -> None: if self.stack: self.stack.pop(); def top(self) -> int: return self.stack[-1][0]; def getMin(self) -> int: if len(self.stack)==0: return None; else: return self.stack[-1][1];