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

主流思路是应用于一个辅助栈,也就是最小元素栈。 每次压栈操作时, 如果压栈元素比当前最小元素更小, 就把这个元素压入最小元素栈, 原本的最小元素就成了次小元素. 同理, 弹栈时, 如果弹出的元素和最小元素栈的栈顶元素相等, 就把最小元素的栈顶弹出.
在这里我是用了一个技巧,每次压栈时压入一个二元组,包括需要压入的元素和当前的最小元素。

def __init__(self):
    self.q = []
def push(self, node):
    # write code here
    curMin = self.min()
    if curMin == None or node < curMin:
        curMin = node
    self.q.append((node, curMin))

def pop(self):
    # write code here
    if len(self.q) == 0:
        return None
    else:
        return self.q.pop()

def top(self):
    # write code here
    if len(self.q) == 0:
        return None
    else:
        return self.q[len(self.q) - 1][0]

def min(self):
    # write code here
    if len(self.q) == 0:
        return None
    else:
        return self.q[len(self.q) - 1][1]