LeetCode155-MinimumStackMinStack

LeetCode155:MinimumStackMinStack设计一个栈，支持push、pop、top操作，可以在常数时间内取回最小元素。push(x)--将元素x压入堆栈。pop()--移除堆栈顶部的元素。top()--获取栈顶元素。getMin()——检索堆栈中的最小元素。设计一个栈，支持push、pop、top，并在常数时间内获取最小元素。push(x)--将元素x压入堆栈。pop()--移除堆栈顶部的元素。top()----获取栈顶元素。getMin()--获取栈中的最小元素。示例：MinStackminStack=newMinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin();-->返回-3.minStack.pop();minStack.top();-->返回0.minStack.getMin();-->返回-2。解题思路：一开始觉得定义一个指向最小值的指针就可以了，后来想到在栈中弹出一个元素的时候，如果弹出的元素是最小值，那么这个指针就需要更改为选择另一个最小元素。没办法，如果你想把push和popping和popping的最小值做到O(1)的时间复杂度，那就只能牺牲空间换取了。您还可以创建一个新堆栈来顺序存储数据的最小值。注意：Python中没有单独的Stack数据结构。其实它的数组是有弹出和推入功能的。您还可以使用collections.deque()数据结构。另外，数据入栈时，需要判断其值是否小于辅助栈栈顶元素的值。如果较小，也应该加入辅助堆栈。并且需要判断辅助栈是否为空。只有不为空才能比较栈顶元素，否则会溢出。其实每次调用一个函数判断是否为空的操作，相对于这道题的运行时间来说，是非常耗时的。对于这个问题是可以避免的。你只需要将最大整数值添加到辅助堆栈作为堆栈的底部元素就可以了。java:classMinStack{Stacks1=newStack<>();//初始化栈Stacks2=newStack<>();//依次将最小值存入辅助栈publicMinStack(){s2.push(Integer.MAX_VALUE);//先将整数的最大值加入栈底，避免判断辅助栈是否为空}publicvoidpush(intx){s1.push(x);if(s2.peek()>=x)s2.push(x);//如果栈顶元素的值小于等于，则加入辅助栈}publicvoidpop(){inttmp=s1.pop();if(tmp==s2.peek())s2.pop();//如果出栈的元素值等于辅助栈栈顶元素的值，则也从辅助栈中出栈}publicinttop(){returns1.peek();//返回栈顶元素}publicintgetMin(){returns2.peek();//返回辅助栈顶元素为最小值value}}Python3:classMinStack:#初始化数据结构（数组），s2作为辅助栈添加最大整数值做栈底，避免判断辅助栈是否为空def__init__(self):self.s1=[]self.s2=[]self.s2.append(sys.maxsize)defpush(self,x:int)->None:self.s1.append(x)#获取顶部栈的元素，直接用数组的负值索引Array[-1]得到最后一个值ifself.s2[-1]>=x:self.s2.append(x)defpop(self)->无：tmp=self.s1.pop()如果tmp==self.s2[-1]:self.s2.pop()deftop(self)->int:returnself.s1[-1]defgetMin(self)->int:返回self.s2[-1]