什么是最小栈？

最小栈也是一个栈(存的元素都是数字)，只不过这种数据结构除了有push、pop、top等和普通栈相同的方法外，还有一个方法get_min用来获取当前栈中的最小元素。

应用场景有哪些？

暂时还没想到

如何实现最小栈，且get_min的时间复杂度为O(1)？

算法思想

首先肯定要有一个变量来保存最小的元素值或者间接的保存最小元素值。
那么这个变量是什么呢？list、dict、还是其他？

一步一步分析，如何才能获取最小值，而且还不影响push、pop、top操作，那么需要保存的数据有两个：

1. 元素的值（这样pop、push的操作才不会受影响）
2. 实时的最小元素（这肯定是一个变化的值）

如果保存最小值使用一个数组保存，那么当执行push、pop的时候，这个数组也要相应更新。这样肯定没办法在O(1)的时间复杂度内完成。如果不能直接保存元素，那我们可以保存栈内元素和最小元素之间的关系，这样在执行pop、push的时候进行计算保存，同时有一个变量保存实时的最小值，那么就实现了O(1)时间内获取最小元素。

思路已经说了，该如何实施呢？

1. 第一次push的时候，把该元素作为最小元素min。
2. 在后面的push操作中，首先判断当前元素num是否小于min,如果不小于min，就向栈中存入元素值data = num-min(这个值肯定大于0，因为num大于min)；如果num小于min，也向栈中存入data = num-min(data小于0)，同时记得更新min值。
3. pop的时候，首先判断栈顶的元素data是否大于0，如果大于0，则pop的值应该是num=data +min（因为存的时候是data = num-min);如果小于0，则pop的时候应该是min，同时要更新min，min = min- data。
4. 同时get_min时直接返回min的值就是整个栈元素中的最小值

算法实现

class MinStack():
    def __init__(self):
        self.stack = list()

    def push(self,num):
        if not len(self.stack):
            self.stack.append(num)
            self.min = num
        else:
            self.stack.append(num - self.min)
            if num < self.min:
                self.min = num

    def p(self):
        print(self.stack,self.min)

    def get_min(self):
        return self.min

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

    def pop(self):
        if not len(self.stack):
            return
        else:
            data = self.stack.pop()
            if data > 0:
                if len(self.stack) == 0:
                    return data # 因为第一次入栈时的值做为最小值，此处不需要加上min
                return data + self.min
            else:
                old = self.min
                self.min = self.min - data
                return old
s = MinStack()
t = [3,33,1,4,5,23,221]
print(t)
for i in t:
    s.push(i)
for i in range(len(t)):
    print(s.get_min(),s.pop())

执行结果：

In [60]: % run min_stack.py
[3, 33, 1, 4, 5, 23, 221]
1 221
1 23
1 5
1 4
1 1
3 33
3 3

图解