*面试题30：包含min函数的栈

题目：
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，时间复杂度应为O(1)。注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

思路：
这道题需要考虑如何实现min函数，只保存一个最小值或者两个并不行，因此运用到另一个缓存栈来进行缓存最小值，压入时候根据不同的情况来对数据栈压入的同时，对缓存栈也进行压入，具体如下：(关于为什么对栈pop函数时需要两个栈都pop笔者暂未弄懂)

30 包含min函数的栈.png

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.minstack = []
    def push(self, node):
        # write code here
        self.stack.append(node)
        if self.minstack ==[] or node < self.min():
            self.minstack.append(node)
        else:
            self.minstack.append(self.min())

    def pop(self):
        # write code here
        if self.stack == [] or self.minstack == []:
            return None
        self.minstack.pop()
        self.stack.pop()

    def top(self):
        # write code here
        return self.stack[-1]
    
    def min(self):
        # write code here
        return self.minstack[-1]

提交结果：