数据结构：min stack & max queue

栈和队列都是常用的数据结构，有时候需要大量进行输出栈/队列里的最大/小值，假如每次都调用min/max函数，效率是O（n），这对于大量操作而言，是不够满意的。因此，可以设计支持平均O（1）时间复杂度返回大小值的min stack和max queue。至于最小最大，原理都是一样的，稍微改一下就可以变成另外一种。

1. min stack

class MinStack:
    def __init__(self):
        self.min = None
        self.stack = []
        
    # @param x, aninteger
    # @return an integer
    def push(self, x):
        if not self.stack:
            self.stack.append(0)
            self.min = x
        else:
            self.stack.append(x - self.min)
            if x < self.min:
                self.min = x

    # @return nothing
    def pop(self):
        x = self.stack.pop()
        if self.stack:
            if x < 0:
                self.min = self.min - x
        else:
            x = self.min
            self.min = None
        print(x)

    # @return aninteger
    def top(self):
        x = self.stack[-1]
        if x > 0:
            return x + self.min
        else:
            return self.min
        
    # @return aninteger
    def getMin(self):
        return self.min

这个实现很巧妙，只用一个数组就实现了最小栈。关键就是不直接放入数值n，而是放入n-min，这样假如n大于min，那么在数组里面体现就是正数，否则是负数，出栈的时候就可以根据情况更新。
假如出栈的时候是正数，说明其入栈的时候不是最小值，可以直接出；否则，说明其就是最小值，因为当时入栈的值其实是n-min_prev，而现在的min其实是n，因此min_prev = n - (n - min_prev)也就是现在的min去减pop出来的值，从而还原n入栈之前的最小值。
同样，top看的数，也是n-min_prev，只不过不用更新min值，假如大于0，说明min还是之前的，相加即可；否则，说明min更新为当前数，直接返回min。
不过有一点需要注意，就是栈为空的时候的处理。
这个做法效率非常高，空间和时间复杂度都是O（1）（因为本来就需要一个栈，不算额外空间复杂度）。

2. max queue

from collections import deque
class maxQ:
    def __init__(self):
        self.D = deque()
        self.Max = deque()

    def push(self, n):
        self.D.append(n)
        while self.Max and self.Max[-1] < n:
            self.Max.pop()
        self.Max.append(n)

    def pop(self):
        if self.Max[0] == self.D[0]:
            self.Max.popleft()
        self.D.popleft()
    
    def getMax(self):
         return self.Max[0] 

队列的情况和栈完全不一样。可以使用两个双端队列，一个专门放max值，每次push进入一个数，就把其值放在max队列里面，并pop掉前面所有比它小的。这是因为，刚刚进来的这个数比之前所有数保留在队列里的时间都久，因此假如有一些值比它还小，因为那些数在它前面出去，所以不可能有机会成为队列的max。相等的值要留下来，这是为了pop。这样max queue的元素是按照降序排列的。
然后就是pop的时候更新max。假如pop出去的是max，那就把它也从max里面pop掉。因为保留了相等的，假如后面有一样的，也不至于全部都删掉。 
max queue的效率低一些，push操作平均是O（1），因为有时候需要连续pop。然后需要额外的O（n）空间。

有了这两个数据结构，max stack和min queue也是可以得到的，原理相同稍作修改，此处不再赘述。