题解 | #包含min函数的栈#
包含min函数的栈
http://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49
class Solution:
def __init__(self):
self.stack = []
self.minstack = []
def push(self, node):
# write code here
if len(self.stack) == 0:
self.stack.append(node)
self.minstack.append(node)
else:
self.stack.append(node)
if node <= self.minstack[-1]:
self.minstack.append(node)
else:
self.minstack.append(self.minstack[-1])
def pop(self):
# write code here
if not self.stack:
return None
else:
self.stack.pop()
self.minstack.pop()
def top(self):
# write code here
if not self.stack:
return None
else:
return self.stack[-1]
def min(self):
# write code here
if not self.minstack:
return None
else:
return self.minstack[-1]
此题的关键是要为min的每次计算设置一个新栈minstack，当新元素入栈时，minstack要检查一下该元素与minstack栈顶元素的大小，若栈顶元素更大则minstack再次入栈栈顶元素，若栈顶元素小于新元素则minstack栈入栈新元素；在出栈时原栈和minstack栈都要出栈栈顶元素，这样每次在弹出minstack栈的栈顶元素时候都能保证得到的元素是最小值。
定义新栈要设置初始化函数，在初始化函数里定义两个栈。
查看8道真题和解析