队列和栈-020-包含min函数的栈

题目描述

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

分析

使用一个辅助栈，用来存储当前栈中的最小值，辅助栈中元素数量和原始栈一样多。每次入栈时，将入栈元素与辅助栈顶元素相比较，如果该元素较小，则将该元素也入辅助栈，否则将辅助栈顶元素再入辅助栈一次。出栈时，辅助栈也要出栈。即保持辅助栈顶元素为当前栈的最小元素值。

代码

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.dataS = [] #data stack
        self.minS = [] #min stack
    
    def push(self, node):
        self.dataS.append(node)
        if not self.minS:
            self.minS.append(node)
        else:
            if self.minS[-1] > node:
                self.minS.append(node)
            else:
                self.minS.append(self.minS[-1])

    def pop(self):
        # write code here
        self.minS.pop()
        return self.dataS.pop()
        
    def min(self):
        # write code here
        if self.minS:
            return self.minS[-1]