[LeetCode][python3]Day10. Min Stack (30-Day LeetCoding Challenge)

30 days! Lets go Lets go!
N2I -2020.04.10

1. My solution

class MinStack:
    def __init__(self):
        self.s=[]
        
    def push(self, x: int) -> None: 
        self.s.append(x)
        
    def pop(self) -> None:
        del self.s[-1]
        
    def top(self) -> int:
        return self.s[-1]
    
    def getMin(self) -> int:
        return min(self.s)

2. A better Solution

class MinStack:
    def __init__(self):
        self.stack = []
        self.min = []
        
    def push(self, x: int) -> None:
        self.stack.append(x)
        if len(self.min) == 0:
            self.min.append(x)
        elif self.min[-1] >= x:
            self.min.append(x)
        
    def pop(self) -> None:
        val = self.stack.pop()
        if val == self.min[-1]:
            self.min.pop()
            
    def top(self) -> int:
        return self.stack[-1]
        
    def getMin(self) -> int:
        return self.min[-1]

Explanation:

This is faster because the getMin() is in constant time. Because the only way to remove element in the structure is pop(), so the min stack here only needs to keep track on the smaller elements in sequence comparing with min[-1].