剑指offer 面试题30. 包含min函数的栈（易）& LeetCode 155. 最小栈（易）

举例分析，双栈问题。

Question

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，**调用 min、push 及 pop 的时间复杂度都是 \(O(1**)\)。

示例: 

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();   --> 返回 0.
minStack.min();   --> 返回 -2.
提示：各函数的调用总次数不超过 20000 次

测试用例

新压入栈的数字比之前的最小值大。 新压入栈的数字比之前的最小值小。 弹出栈的数字不是最小元素。 弹出栈的数字是最小元素。

本题考点

考查应聘者分析复杂问题的思维能力。在面试的时候，很多应聘者都止步于添加一个变量保存最小元素的思路。其实只要举个例子，多做几次入栈、出栈的操作就能看出问题，并想到也要把最小元素用另外的辅助栈保存。当我们面对一个抽象复杂的问题的时候，可以用几个具体的例子来找出规律。找到规律之后再解决问题，就容易多了。 考查应聘者对栈的理解。

Intuition

第一反应可能是每次压入一个新元素进栈时，将栈里的所有元素排序，让最小的元素位于栈顶，这样就能在 \(O(1)\) 时间内得到最小元素了。但这种思路不能保证最后压入栈的元素能够最先出栈，因此这个数据结构不再是栈了。

接着想到在栈里添加一个成员变量存放最小的元素。每次压入一个新元素进栈的时候，如果该元素比当前最小的元素还要小，则更新最小元素。面试官听到这种思路之后就会问：如果当前最小的元素被弹出栈了，那么如何得到下一个最小的元素呢？

是不是可以把每次的最小元素（之前的最小元素和新压入栈的元素两者的较小值）都保存起来放到另外一个辅助栈里呢？

Snipaste_2020-05-09_13-34-06.png

Code

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.items = []
        self.min_items = []
        self.size = -1  # 初始值为-1 下标从0开始


    def push(self, x: int) -> None:

        # 先更新辅助栈 
        if self.size == -1:  # 第一次添加
            self.min_items.append(x)
        elif x < self.min_items[self.size]:
            self.min_items.append(x)
        else:
            self.min_items.append(self.min_items[self.size])

        # 再更新主栈
        self.items.append(x)
        self.size += 1


    def pop(self) -> None:
        if self.size > -1:
            res = self.items[self.size]
            del self.items[self.size]
            del self.min_items[self.size]
            self.size -= 1
            return res
        else:
            raise ValueError

    def top(self) -> int:
        if self.size > -1:
            res = self.items[self.size]
            return res
        else:
            raise ValueError


    def min(self) -> int:
        if self.size > -1:
            res = self.min_items[self.size]
            return res
        else:
            raise ValueError



if __name__ == "__main__":

    # Test Case 1
    # ["MinStack","push","push","push","min","pop","top","min"]
    # [[],[-2],[0],[-3],[],[],[],[]]
    minStack = MinStack()
    minStack.push(-2)
    minStack.push(0)  # 新压入栈的数字比之前的最小值大。
    minStack.push(-3)  # 新压入栈的数字比之前的最小值小。
    minStack.push(1)
    print(minStack.pop())     # 返回 1.  弹出栈的数字不是最小元素。
    print(minStack.min())     # 返回 -3. 
    print(minStack.pop())     # 返回 -3. 弹出栈的数字是最小元素。
    print(minStack.top())     # 返回 0.
    print(minStack.min())     # 返回 -2.

    # Test Case 2
    # ["MinStack","push","min"]
    # [[],[-3],[]]
    minStack = MinStack()
    minStack.push(-3)
    print(minStack.min())     # 返回 -3.