155. Min Stack (Python)

Related Topic

Stack.

Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) – Push element x onto stack.
• pop() – Removes the element on top of the stack.
• top() – Get the top element.
• getMin() – Retrieve the minimum element in the stack.

Note

Do not modify the linked list.

Sample I/O

Example 1

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints

• Methods pop, top and getMin operations will always be called on non-empty stacks.

Methodology

Push, pop and top are basic stack operations and they are easy to implemented by list. However, the hard part is getMin(). To implement Push, pop and top, we have to keep the original order. To get min we somehow need to create extra space (min_stack) to stor the value in min order. If so, we have to compare the number with others each time when we insert the number into min_stack and this will cost a lot. The better way is to use index and priority level to mark each number in min_stack.

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.index = -1
        self.min_stack = []
        self.min_index = -1
        self.min_value = float("inf")

    def push(self, x: int) -> None:
        if x < self.min_value:
            self.min_stack.append([x,1])
            self.min_value = x
            self.min_index += 1
        elif x == self.min_value:
            self.min_stack[self.min_index][1]+=1
        self.stack.append(x)
        self.index += 1

    def pop(self) -> None:
        if self.index < 0:
            return
        value = self.stack.pop()
        if value == self.min_value:
            self.min_stack[self.min_index][1] -= 1
        if self.min_stack[self.min_index][1] == 0:
            self.min_stack.pop()
            self.min_index -= 1
            if self.min_index != -1:
                self.min_value = self.min_stack[self.min_index][0]
            else:
                self.min_value = float("inf")
        if self.min_stack == -1: return
        self.index -= 1
    def top(self) -> int:
        if self.index < 0:
            return
        return self.stack[self.index]
    def getMin(self) -> int:
        return self.min_value

BigO

No need to iterate the stack or list, all operations push, pop, top and getMin are O(1)