[LeetCode] Min Stack (Python3)

leetcode

Thoughts:

The first thing that came to my mind was to maintain a min value. However, if there are multiple min value in the stack, it’s impossible to check whether the min value has changed when popping out a value.

Luckily, the specialty of stacks make sure that you always know what value is popped. Therefore, by maintaining “the current min value” stack allows us to easily trace back previous min values.

When pushing a new value into the stack, check the min value and pop in the new min (whether it’s changed or not) into the second stack as well. Therefore, when you are popping elements, you simply need to pop element from the second stack to restore previous min value. This works because if the min is updated then it must because of the top value in stack, so if you pop the top element then it will go back to before.

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

class MinStack:

    def __init__(self):
        # do intialization if necessary
        self.stack = []
        self.stack2 = []
        self.minimum = None
    """
    @param: number: An integer
    @return: nothing
    """
    def push(self, number):
        # write your code here
        self.stack.append(number)
        if len(self.stack2) == 0 or number <= self.stack2[-1]:
            self.stack2.append(number)

    """
    @return: An integer
    """
    def pop(self):
        # write your code here
        if self.stack[-1] == self.stack2[-1]:
            self.stack2.pop()
        return self.stack.pop()
    """
    @return: An integer
    """
    def min(self):
        # write your code here
        return self.stack2[-1]