Leetcode-155-最小栈

发表于 | 分类于 ，

创建额外空间来保存min栈，来弥补python-list的线性表的不足。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = [] 
        self.min = []
        
    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        if not len(self.stack):
            self.min.append(x) 
        else:
            if x <= self.min[-1]: 
                self.min.append(x)
            
        self.stack.append(x) 

    def pop(self):
        """
        :rtype: void
        """
        if self.stack[-1] == self.min[-1]:
            self.min.pop()
            
        self.stack.pop()

    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1] 

    def getMin(self):
        """
        :rtype: int
        """
        return self.min[-1]

由于python内置函数中的min（）方法会用到O（n）的时间复杂度。

参考：https://www.jianshu.com/p/a8fa3d31aa40

所以本题设计的重心在于怎样提取栈中最小的元素，在本栈中创建了另外一个线性表self.min来存储栈中最小的元素–压入一个比之前小的数的时候，同时压入min中，推出的时候若正式栈和min栈的数相等，则同时推出

收到