LeetCode-155-最小栈

原题链接：https://leetcode-cn.com/problems/min-stack/

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

image.png

解题思路：

1. 想要O(1)复杂度的实现检索栈中最小元素，维护两个列表，stack用来存储入栈出栈的值，min_stack用来存储出入栈的局部最小值，且降序排列；
2. 当min_stack中已有值，当push入新的值x时，需要对比min_stack[-1]，比其大的无须加入；
3. 当pop()操作时，需要判断stack.pop()的值是否是min_stack[-1]，如果是，min_stack也需要pop()栈顶的值；
4. 因此实现O(1)操作的获取最小元素，即由min_stack[-1]的值来呈现。

Python3代码：

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or self.min_stack[-1] >= x:
            self.min_stack.append(x)

    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def min(self) -> int:
        return self.min_stack[-1]