[LeetCode][Python] 155. Min Stack

- 문제 링크: https://leetcode.com/problems/min-stack/

- 난이도: Medium

 

스택을 구현하는 문제인데, 현재 스택의 최소값을 가져오는 getMin 연산을 구현하는게 관건인 문제이다. O(1) 시간복잡도가 필요하다

스택의 각 노드가 그 지점에서의 최소값을 들고 있으면 된다.

class MinStack:

    def __init__(self):
        self.stack = []  # (val, current_min)

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

    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]