问题:实现一个带有取最小值min方法的栈,min方法将返回当前栈中的最小值。
你实现的栈将支持push,pop 和 min 操作,所有操作要求都在O(1)时间内完成。
如下操作:push(1),pop(),push(2),push(3),min(), push(1),min() 返回 1,2,1
思路:一个栈每次存入一个数组,这个数组里面包含两个element,一个是每次传入的值,另一个是目前传入的数里最小的数。
这样无论任何时候,我们都可以找到当前的min。
Python3
class MinStack(object):
def __init__(self):
# do some intialize if necessary
self.stack = []
self.minstack = []
def push(self, number):
# write yout code here
self.stack.append(number)
if len(self.minstack) == 0 or number <= self.minstack[-1]:
self.minstack.append(number)
def pop(self):
# pop and return the top item in stack
if self.stack[-1] == self.minstack[-1]:
self.minstack.pop()
return self.stack.pop()
def min(self):
# return the minimum number in stack
return self.minstack[-1]
stack基于数组实现,。在python3中,二维数组是[][]表示(同java),而不是[ , ]。
除此之外,要表示数组的最后一个,在python3中可以用-1表示。即a[-1] 表示数组里面最后一位。