leetcode-design

155. Min Stack.py

class MinStack:
    """
    Problem Clarificaiton:
        Can I assumm all valid operations to similify code at the moment.

    In the end, ask any place that you want me to modify.
    All opeations can be done in O(1)
    Thought Process:
        We somehow need a way to ke track of a minimum--> Heap and Binary search tree
        
        Heap retrive min element in O(1), insert/delete/search take O(logn) same as BST. So, it's not good enough.
        
        We need two stack. One is normal stack. Another stack only keep the smallest element.
    
    Ref:
        https://www.youtube.com/watch?v=O1AF77qVWjg&ab_channel=MaxMing
    """
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_stack = [float("inf")]
        

    def push(self, x: int) -> None:
        if x <= self.min_stack[-1]:
            # 相等也要push到最小stack因為, 如果pop掉另外一個最小的, 這個相等的還是最小.
            self.min_stack.append(x)
        self.stack.append(x)
            

    def pop(self) -> None:
        if self.stack[-1] == self.min_stack[-1]:
            _ = self.min_stack.pop()
        return self.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(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()