1 题目

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。 —来源Leetcode

实例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.

2 解题思路

思路1： min得到最小值，将栈中元素进行排序得到最小值，但没有一种排序算法是能够在O(1)复杂度得到最小元素的；
思路2： 若栈中最小元素弹出了，第二次弹出则需要有次小元素，因此考虑使用一个辅助的栈记录最小值。在弹出时，将两个栈的数据都弹出。

图片来源： --来源b站：香辣鸡排蛋包饭

3 代码实现

class MinStack(object):

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

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack1.append(x)
        if len(self.stack2) != 0:
            val = min(self.stack2[-1], x)
            self.stack2.append(val)
        else:
            self.stack2.append(x)

    def pop(self):
        """
        :rtype: None
        """
        self.stack1.pop()
        self.stack2.pop()

    def top(self):
        """
        :rtype: int
        """
        return self.stack1[-1]

    def min(self):
        """
        :rtype: int
        """
        return self.stack2[-1]