数据结构与算法:第五周作业二:最小栈
程序员文章站
2022-06-03 13:45:54
...
题目描述
链接:https://leetcode-cn.com/problems/min-stack/
思路:
用一个辅助栈来记录最小值,最小值总是在栈顶,所以getMin(),返回-1的索引即可。
对于最小栈入栈的情况有三种:
1.最小栈为空,入栈。
2.当前元素<=栈顶元素,入栈。
3.当前元素>当前元素,出栈。
在pop()方法里,需要比较pop()的元素是否是最小栈的栈顶元素,如果是,那么最小栈的栈顶元素也需要被pop()。
代码
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.elem=[]
self.min=[]
def push(self, x: int) -> None:
self.elem.append(x)
if not self.min or x<=self.min[-1]:
self.min.append(x)
def pop(self) -> None:
if not self.elem:
raise ValueError('in MinStack pop()')
a=self.elem.pop()
if a==self.min[-1]:
self.min.pop()
def top(self) -> int:
if not self.elem:
raise ValueError('in MinStack top()')
return self.elem
def getMin(self) -> int:
return self.min[-1]