题解 | #包含min函数的栈#

NC90 包含min函数的栈

描述 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有： push(value):将value压入栈中 pop():弹出栈顶元素 top():获取栈顶元素 min():获取栈中最小元素

数据范围：操作数量满足0<=n<=300,输入的元素满足|val|<=10000

进阶：栈的各个操作的时间复杂度是O(1)，空间复杂度是O(n)

思路：其它都还好，主要是min()这个方法要求时间复杂度为O(1)，我本来觉得不可能，因为栈是无序的，在无序数组中找最小值，应该要遍历一遍数组。看评论才知道，是用空间换时间。专门存了一个辅助栈来保存最小值，这样就简单了，算法也没啥好说的。我看到空间复杂度为O(n)，以为就是栈的长度，这样其实空间复杂度是O(2n)了

min函数算法：每次进来一个元素，一个栈直接存入，另一个辅助栈会判断，如果当前元素小于辅助栈栈顶（即栈的最小值）时，将该元素放入，否则放入辅助栈栈顶元素。每次取出也是栈和辅助栈一起取出。

class Solution:
    data = []
    minData = []
    def push(self, node):
        # write code here
        self.data.append(node)
        if len(self.minData) == 0:
            self.minData.append(node)
        elif node < self.minData[len(self.minData)-1]:
            self.minData.append(node)
        else:
            self.minData.append(self.minData[len(self.minData)-1])
    def pop(self):
        # write code here
        self.data.pop()
        self.minData.pop()
    def top(self):
        # write code here
        return self.data[len(self.data)-1]
    def min(self):
        # write code here
        return self.minData[len(self.minData)-1]