155. Min Stack

Min Stack - LeetCode

1. event를 flag로 해서 처리하는 풀이

from heapq import *


class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []
        self.events = [0] * 30000
        self.event_cnt = 0

    def push(self, val: int) -> None:
        self.stack.append((val, self.event_cnt))
        heappush(self.min_stack, (val, self.event_cnt))
        self.events[self.event_cnt] = 1
        self.event_cnt += 1

    def pop(self) -> None:
        popped_val, popped_event = self.stack.pop()
        self.events[popped_event] = 0

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

    def getMin(self) -> int:
        while self.events[self.min_stack[0][1]] == 0:
            heappop(self.min_stack)
        return self.min_stack[0][0]

 

이중 우선순위 큐와 같은 문제를 풀 때처럼 push, pop을 하나의 이벤트로 생각하고, 각각의 이벤트에 번호를 달아준다.

스택에서 빠질 때 해당 이벤트를 꺼주고, min_stack에선 가장 최솟값인 이벤트가 꺼지지 않을 때까지 heappop 한 뒤 최솟값을 구한다.