因此,想到构造一个辅助栈S_helper,每次往栈S中添加到一个元素时,辅助栈S_helper都会在栈顶添加一次当前S里最小的元素值。这样每次调用min时,只需要返回辅助栈的栈顶元素即可。 当然在删除S中的栈顶元素时,也会删除S_helper中的栈顶元素。
注意,要明确每次在辅助站中添加的元素是谁。
若新添加的元素小于辅助栈 的栈顶元素(也就是小于当前S中的最小元素),那么就在栈顶添加新的value。
如果新添加的value大于辅助栈的栈顶元素,那么就继续在辅助栈中添加辅助栈的栈顶元素即可。
代码实现:
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.S = []
self.S_helper = []
def push(self, node):
self.S.append(node)
#如果辅助站为空,或新来的node值大于辅助站的栈顶元素,
# 那么就更新辅助站的栈顶元素为最小值
if len(self.S_helper) == 0 or node < self.S_helper[-1]:
self.S_helper.append(node)
else:
self.S_helper.append(self.S_helper[-1])
def pop(self):
res = self.S.pop()
res_helper = self.S_helper.pop()
return res
def top(self):
return self.S[-1]
def min(self):
return self.S_helper[-1]