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

题目描述

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

知识点

栈

Qiang的思路

对于这个问题中描述的这个栈和普通的栈的区别在于具有求最小元素的功能，那么，这个栈应该不止能将数据压入、弹出，还能够获得栈中的最小元素。显然，我们可以维护一个最小元素，当数据入栈时，需要将当前最小元素进行更新，当数据出栈时也需要将最小的数据进行更新，但是这样每次出栈和入栈的时候都会重新计算一下当前的最小元素，时间复杂度肯定是高的。

所以，可以考虑空间换时间，维护一个和栈绑定的最小元素栈，这个最小元素栈中存放着与题目要的栈对应的最小元素值，这样，每次要求最小的元素时，我们只需要将当前状态对应的最小元素获得即可。同时，因为两者是绑定的，所以当更新题目要求的栈时需要同步的对最小元素栈进行更新。但压入元素时，将上一时刻的最小元素和当前元素进行对比，更小的元素为当前时刻的最小元素，当弹出元素时，只需要将对应状态的最小元素弹出即可。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.m=[]
        self.s=[]
        
    def push(self, node):
        # write code here
        self.m.append(self.m[-1] if self.m!=[] and self.m[-1]<node else node)
        self.s.append(node)
        
    def pop(self):
        # write code here
        if self.s==[]:
            return None
        self.m.pop(-1)
        return self.s.pop(-1)
    
    def top(self):
        # write code here
        return self.s[-1]
    
    def min(self):
        # write code here
        return self.m[-1]

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。