Stack是一种常用的数据结构。除了在数据结构上，栈的概念使用得很广：

  1. 函数调用栈
  2. 和内存有关的堆栈
  3. 数据结构中的栈结构

数据结构中的栈通常包含四种操作：

  1. push 把元素压入栈
  2. pop 把栈顶元素弹出
  3. top 获取栈顶元素
  4. empty 判断栈是否为空

上面的四种操作都在O(1)内完成。那么问题来了，如果我们要为栈添加两个接口max、min分别获取当前栈的最大、最小值且在O(1)内完成，该如何实现呢？

一种直观但错误的思路是：使用两个变量分别保存最大、最小值。错误在于如果我们已经弹出了最大或最小值了，那么该如何确定当前栈的最大或最小值呢？方法肯定有，但无法做到O(1)

解决这个问题，离不开时间、空间的均衡思想。当我们对算法的时间复杂度有更改的要求，可以通过牺牲空间来解决，反之亦然。当然，这不是定理，而是一种实践经验。

我们可以通过两个辅助栈的来分表保存栈各阶段的max、min值。这样一来我们就需要三个基本栈了。我们先来实现一个基本栈，然后慢慢梳理实现过程。

基本栈的实现

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
class Node:
    
    def __init__(self, value):
        self.value = value
        self.next = None

class Stack:

    def __init__(self):
        self._top = None

    def __repr__(self):
        return '<Stack>'

    def push(self, value):
        elem = Node(value)
        elem.next = self._top
        self._top = elem

    def pop(self):
        if not self.empty():
            elem = self._top
            self._top = elem.next
            return elem.value
        return None
        
    def top(self):
        if self.empty():
            return None
        return self._top.value

    def empty(self):
        return self._top is None

空间换时间

我们把能弹出最大最小元素的栈命名为MStack。MStack需要三个基本栈，分别为cstack、maxstack、minstack。cstack像普通栈一样的操作；maxstack每次比较过程只存储当前栈的最大元素（并不是之保存一个最大元素）；minstack每次比较过程只存储当前栈的最小元素。三个栈的元素数量是一一对应的。下面见具体实现。

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
43
44
45
46
47
48
49
50

class MStack:
    
    def __init__(self):
        self.cstack = Stack()
        self.maxstack = Stack()
        self.minstack = Stack()
        self.max = None
        self.min = None

    def __repr__(self):
        return '<Stack>'

    def push(self, value):
        if self.max is None:
            self.max = value
            self.maxstack.push(value)
        else:
            if self.max < value:
                self.maxstack.push(value)
                self.max = value
            else:
                self.maxstack.push(self.max)

        if self.min is None:
            self.min = value
            self.minstack.push(value)
        else:
            if self.min > value:
                self.minstack.push(value)
                self.min = value
            else:
                self.minstack.push(self.min)

        self.cstack.push(value)

    def top(self):
        return self.cstack.top()

    def pop(self):
        self.maxstack.pop()
        self.minstack.pop()
        return self.cstack.pop()

    def getmax(self):
        return self.maxstack.top()

    def getmin(self):
        return self.minstack.top()

实现MStack的关机是（1）采用辅助栈保存最大、最小状态（2）push操作处理好当前栈的max、minmax、min