155. Min Stack

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/min-stack
• topics: Stack

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

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Idea:

Use stack

class MinStack:
 
    def __init__(self):
        self.stack = deque()
        self.min_stack = deque()        
 
    def push(self, val: int) -> None:
        self.stack.append(val)
        if self.min_stack:
            self.min_stack.append(min(val, self.min_stack[-1]))
        else:
            self.min_stack.append(val)
 
    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()
 
    def top(self) -> int:
        return self.stack[-1]
 
    def getMin(self) -> int:
        return self.min_stack[-1]
        
 
 
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()