155。最小栈题目来源：https://leetcode-cn.com/problems/min-stack题目设计一个支持push、pop、top操作，并且可以在常数时间内取回栈的最小元素。push(x)–将元素x压入堆栈。pop()-移除堆栈顶部的元素。top()-获取栈顶元素。getMin()-检索堆栈中的最小元素。示例：输入：["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]]输出：[null,null,null,null,-3,null,0,-2]解释：MinStackminStack=newMinStack();minStack。推（-2）；minStack.push（0）；minStack.push（-3）；minStack.getMin（）；-->返回-3.minStack.pop();minStack.top();-->返回0.minStack.getMin();-->返回-2。注意：pop、top和getMin操作总是在非空堆栈上调用。解题思路：辅助栈这道题我们考虑使用辅助栈和数据栈同步的方法来处理。如标题所示，pop、top和getMin操作总是在非空堆栈上调用。那么我们首先定义一个数据栈来实现这些功能。题目还要求可以在常数时间内取回最小元素的栈。这里我们使用辅助栈来实现辅助栈中的栈顶保持当前的最小值，从而实现时间复杂度恒定的操作。具体代码实现如下。代码实现类MinStack:def__init__(self):"""在这里初始化你的数据结构。"""self.data=[]self.tmp=[]defpush(self,x:int)->None:#input入栈时，同时考虑数据栈和辅助栈self.data.append(x)#如果辅助栈为空，或者当元素小于等于辅助栈的栈顶元素时，将元素压入stack#否则辅助栈中栈顶元素再次入栈iflen(self.tmp)==0orx<=self.tmp[-1]:self.tmp.append(x)else:self.tmp.append(self.tmp[-1])defpop(self)->None:#ifself.data:#self.data.pop()#self.tmp.pop()#标题要求说明这是一个非空栈，所以不做判断#如果需要判断可以按上面的方法做self.data.pop()self.tmp.pop()deftop(self)->int:#需要判断同pop()returnself.data[-1]defgetMin(self)->int:#需要判断同pop()returnself.tmp[-1]#你的MinStack对象将被实例化并这样调用：#obj=MinStack()#obj.push(x)#obj.pop()#param_3=obj.top()#param_4=obj.getMin()实现上面的结果就是使用辅助栈。根据栈先进先出的性质，解决问题的主要内容《155. 最小栈》欢迎关注微信公众号《书所集录》
