题目

难度：★☆☆☆☆
类型：栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。

示例

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

解答

和普通的栈不同的是，我们的栈新增了一个功能，获得当前栈中的最小值，这里，我们通过额外增加一个栈来实现：

1. 定义两个栈，一个基本栈（stack），用于存储每个元素，一个最小栈（min），其栈顶元素代表基本栈中的最小值，这两个栈在init函数中初始化为空栈；

2. 往基本栈中压入元素的同时，最小栈中也要压入一个值，这个值是压入元素后的基本栈中的最小值，如何得到这个值？我们只需要取出最小栈中的栈顶元素，因为这个元素代表了基本栈中还没有压入元素时的最小值，通过与被压入的元素进行比较，把其中更小的数值压入到最小栈中，保证两个栈中元素个数相同，如果最小栈为空则直接压入该元素即可；

3. 在弹出栈时，不仅要弹出基本栈中的元素，最小栈中的元素也要同步弹出；

4. 获取当前栈的最小值，返回最小栈的栈顶元素即可，其他功能和普通栈相同。

class MinStack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []                         # 定义一个基本栈，用于存储每个元素
        self.min = []                           # 定义一个最小栈，其栈顶元素是当前基本栈中的最小值

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack.append(x)                    # 把元素压入栈中
        if not self.min or x < self.min[-1]:    # 如果最小栈为空或新元素比基本栈的最小值还要小
            self.min.append(x)                  # 该元素是目前出现的最小值，压入最小栈
        else:                                   # 否则
            self.min.append(self.min[-1])       # 将最小栈中的栈顶元素复制一遍压入最小栈

    def pop(self):
        """
        :rtype: None
        """
        self.min.pop()                          # 弹出最小栈中的元素，保证两个栈元素个数相同
        return self.stack.pop()                 # 弹出基本栈中的元素

    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1]                   # 返回基本栈的栈顶元素

    def getMin(self):
        """
        :rtype: int
        """
        return self.min[-1]                     # 返回最小栈的栈顶元素

如有疑问或建议，欢迎评论区留言~