面试题21-包含min函数的栈

Posted on Edited on In

题目

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.

解题

My first commit

没有降低min的复杂度, 遍历一次时间复杂度为O(N)

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
class MinStack:
    stack = []

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []


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


    def pop(self) -> None:
        top_item = self.stack[-1]
        self.stack = self.stack[:-1]
        return top_item


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


    def min(self) -> int:
        # stack_items = self.stack
        minimun = self.stack[0]
        for cnt in range(len(self.stack)-1):
            if self.stack[cnt+1] <= minimun:
                minimun = self.stack[cnt+1]
        return minimun

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

Takeaway from others

面试题30. 包含 min 函数的栈（辅助栈，清晰图解）

Picture1.png

  • 利用辅助栈来降低复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MinStack:
    def __init__(self):
        self.A, self.B = [], []

    def push(self, x: int) -> None:
        self.A.append(x)
        if not self.B or self.B[-1] >= x:
            self.B.append(x)

    def pop(self) -> None:
        if self.A.pop() == self.B[-1]:
            self.B.pop()

    def top(self) -> int:
        return self.A[-1]

    def min(self) -> int:
        return self.B[-1]

总结

  1. python 中 slice:

    Understanding slice notation

    1
    a[start:stop:step]

    is equivalent to:

    1
    a[slice(start, stop, step)]

  2. 常犯错误: 循环中不能改变循环变量!