包含min函数的栈

发表于 | 分类于 | 次

###题目

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

解题思路

栈stack保存数据，辅助栈assist保存依次入栈最小的数，stack中依次入栈，6，5，8，4，3，9；assist依次入栈，6，5，4，3。每次入栈的时候，如果入栈的元素比assist中的栈顶元素小或等于则入栈，否则不如栈。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# -*- coding:utf-8 -*-
assist = []
stack = []
class Solution:
    def push(self, node):
        stack.append(node)
        if len(assist) == 0:
            assist.append(node)
        elif node < assist[-1]:
            assist.append(node)
            
    def pop(self):
        if len(stack) > 0:
            tmp = stack.pop()
            if tmp == assist[-1]:
                assist.pop()
        else:
            return None
    def min(self):
        return assist[-1]