题目描述：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
分析：题目要求常数时间内完成，那么排序的操作就不可以放在getmin当中，最直接的就是引入另外一个空间 ,当然效率也比较低：
class MinStack: def __init__(self): self.stack=[] self.tmp=[]#临时空间 def push(self, val: int) -> None: self.stack.append(val) self.tmp.append(val) for i in range(len(self.tmp)-1): if self.tmp[i]<self.tmp[i+1]: self.tmp[i],self.tmp[i+1]=self.tmp[i+1],self.tmp[i] def pop(self) -> None: del self.tmp[self.tmp.index(self.stack[-1])] del self.stack[-1]#前后顺序不能调换，否则就会以更新后的self.stack[-1]删除，造成错误！！ def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.tmp[-1] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(val) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin()
0.0看了官方题解，可以仅使用一个空间满足，时间上快了很多！！
下面是优化后的代码：
class MinStack: def __init__(self): self.stack=[]#尝试仅使用一个空间 每个元素是元组 储存当前压栈对象和栈最小值 def push(self, val: int) -> None: if not self.stack: self.stack.append((val,val)) else: self.stack.append((val,min(self.stack[-1][1],val))) def pop(self) -> None: del self.stack[-1] def top(self) -> int: return self.stack[-1][0] def getMin(self) -> int: return self.stack[-1][1] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(val) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin()
其实也挺容易理解，就是把最关键的两个变量，min元素和压栈元素存储起来，压栈元素与上一轮压栈后栈的最小值比较，形成结果。就是一个前后联系的过程 满足了栈先进后出 后进先出的特点，比如bcd在a底下，a作为栈顶，g是待压栈元素，只需g和abcd比较
