155. Min Stack

[fockspaces]

stack

given that each function should only perform in O(1) time, we need to get the min value directly. we can use two stack for tracking, the stack and the min_stack

min_stack will only be appended when the current value <= top and only be deleted when it's the same value with the stack.

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        pop_val = self.stack.pop()
        if pop_val == self.min_stack[-1]:
            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()

[fockspaces]

actually it can use only one stack, each item store a tuple (val, current_min)

class MinStack:

    def __init__(self):
        self.stack = []

    def push(self, val: int) -> None:
        stack_top = self.stack[-1][1] if self.stack else val
        self.stack.append((val, min(val, stack_top)))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]