155. Min Stack

https://leetcode.cn/problems/min-stack/solutions/9036/min-stack-fu-zhu-stackfa-by-jin407891080

解题思路：

借用一个辅助栈 min_stack，用于存获取 stack 中最小值。

算法流程：

push() 方法：每当push()新值进来时，如果小于等于 min_stack 栈顶值或者为第一个元素时，则一起 push() 到 min_stack，即更新了栈顶最小值；
pop() 方法：判断将 pop() 出去的元素值是否是 min_stack 栈顶元素值（即最小值），如果是则将 min_stack 栈顶元素一起 pop()，这样可以保证 min_stack 栈顶元素始终是 stack 中的最小值。
getMin()方法：返回 min_stack 栈顶即可。 min_stack 作用分析：

min_stack 等价于遍历 stack所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈。相当于给 stack 中的降序元素做了标记，每当 pop() 这些降序元素，min_stack 会将相应的栈顶元素 pop() 出去，保证其栈顶元素始终是 stack 中的最小元素。

复杂度分析：

时间复杂度 O(1) ：压栈，出栈，获取最小值的时间复杂度都为 O(1) 。空间复杂度 O(N) ：包含 N 个元素辅助栈占用线性大小的额外空间。

GIF图：https://pic.leetcode-cn.com/28724fa9f92b6952f7fdaf8760edd1dea850b137c22df28751f1cdd4d2680992-155.gif

最小栈法

python

class MinStack:

    def __init__(self):
        self.stack = []
        self.minStack = []

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

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

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

    def getMin(self) -> int:
        if self.minStack:
            return self.minStack[-1]
        # return

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()