包含min函数的栈（算法21）

问题

问题：定义栈的数据结构，在该类型中实现一个得到栈最小值的min函数。调用min、push、pop操作的时间复杂度都是$O(1)$。

这道题和先前文章O(1)时间复杂度获取Stack中最大最小值类似，解决思路见该文章。这里给出具体实现。

原理：

具体的原理参考前面提及的文章。它本质是空间换时间的思路。

实现：

编写常规Stack

先编写一个常规的栈，处于代码的简洁，这列不添加边界异常处理。例如对空栈调用pop直接出错，让外层代码处理异常。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Stack:

    def __init__(self):
        self._s = []

    def push(self, item):
        self._s.append(item)

    def pop(self):
        return self._s.pop()

    def empty(self):
        return len(self._s) == 0

    def top(self):
        if self.empty():
            return None
        return self._s[-1]

包含min函数的Stack

下面实现包含min函数的栈。每次push操作都会在_min栈上保存当前的最小值，起到排序的作用，具体看如下代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class StackWithMin:

    def __init__(self):
        self._common = Stack()
        self._min = Stack()

    def push(self, item):
        self._common.push(item)
        if self._min.empty():
            self._min.push(item)
        else:
            if self._min.top() >= item:
                self._min.push(item)
            else:
                self._min.push(self._min.top())

    def pop(self):
        self._min.pop()
        return self._common.pop()

    def min(self):
        return self._min.top()

类比一下

Python代码本身很简洁，根据代码也可以看出min栈的思路。对吧？类似地，如果实现带max操作的栈，思路也一样。只需要把push操作的大小判断即可。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class StackWithMax:

    def __init__(self):
        self._common = Stack()
        self._max = Stack()

    def push(self, item):
        self._common.push(item)
        if self._max.empty():
            self._max.push(item)
        else:
            if self._max.top() < item:
                self._max.push(item)
            else:
                self._max.push(self._max.top())

    def pop(self):
        self._max.pop()
        return self._common.pop()

    def max(self):
        return self._max.top()

根据实现，很容易把StackWithMax和StackWithMin结合在一起，实现具有min、max函数的栈。