包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。在该栈中，调用min，push和pop的时间复杂度都是O（1）。

思路

首先常规的压入和弹出可以在一个正常的栈中进行。
这道题要解决的问题在于最小值的保存。如果只保存最小值，当这个值恰好被弹出之后，再查询最小值的时候，就没有了。所以还需要这里要构建一个辅助的保存最小值的栈每次元素压入的时候，比较当前值与栈里最小值的大小，如果当前值更小就把他压入最小栈，这样目前栈里的最小值是当前值。如果还是最小栈里的值小，那么再压一次这个最小值。这样一是保证两个栈数量一样，二是保证当前长度中的最小值是正确的。
这里的核心思想就是建立辅助栈，和辅助栈的操作处理。

class Solution:
    stack = []
    minList = []
    def push(self, node):
        self.stack.append(node)
        if len(self.minList)  < 1:
            self.minList.append(node)
        else:
            val = min(self.minList[-1],node)
            self.minList.append(min(self.minList[-1],node))
    def pop(self):
        if self.stack is None:
            return None
        self.minList.pop()
        ans = self.stack.pop()
        return ans
    def top(self):
        if self.stack is None:
            return None
        ans = self.stack.pop()
        return ans
    def min(self):
        if self.minList is None:
            return None
        ans = self.minList[-1]
        return ans