1 问题
如何利用python在常数时间里检测到最小的元素栈。
2 方法
用一个变量来记录最小值，需要的时候直接取到就可以实现目标。 借助一个辅助栈，由于入栈出栈操作是动态的，所以最小值也是动态的，我们可以用一个栈来维护每一个状态下的最小值。具体实现：
代码清单 1
代码语言：text复制Class Stack:
def __init__(self):
#initialize your data structure here.
self.data_stack = []
self.min_stack = []
#1. 当第一个元素入栈时，它就是当前栈的最小值，于是Push到min_stack
#2. 当入栈元素小于min_stack的栈顶元素时，说明该元素入栈之后是当前状态的最小值，因此将它push到min_stack中
#3. 当入栈元素大于min_stack的栈顶元素时，说明该元素入栈之后当前状态的最小值没有发生改变，因此将原来的最小值（就是min_stack栈顶元素）push到min_stack中
def push(self, x: int) -> None:
self.data_stack.append(x)
if self.min_stack == [] or self.min_stack[-1] > x:
self.min_stack.append(x)
else:
self.min_stack.append(self.min_stack[-1])
def pop(self) -> None:
self.data_stack = self.data_stack[0:-1]
self.min_stack = self.min_stack[0:-1]
def top(self) -> int:
return self.data_stack[-1]
Def Min(self) -> int:
return self.min_stack[-1]3 结语
这个问题有个注意的点是在常数时间内检索到。遍历栈或者用一些排序方式固然可以找到最小值，但是无法在满足常数时间的要求。我们这里借助一个辅助栈，由于入栈出栈操作是动态的，所以最小值也是动态的，我们可以用一个栈来维护每一个状态下的最小值。熟练的利用python栈章节的知识点，push,pop,top等熟练的运用可以学习到不局限于书上的知识点。
