[Leetcode] 155. Min Stack

문제

https://leetcode.com/problems/min-stack/description/?envType=study-plan-v2&envId=top-100-liked

풀이

getMin을 O(1)로 구현하는것이 핵심이다.

만약 getMin을 O(1)이 아닌 O(N)으로 하게 되면 다음과 같은 코드가 된다. 궁금해서 제출해보니 해당 코드로 AC를 받을 수는 있었다.

class MinStack:

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

    def push(self, val: int) -> None:
        self.stack.append(val)

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

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

    def getMin(self) -> int:
        return min(self.stack) # O(N)이라 터질것

getMin을 O(1)로 만들기 위한 방법을 고민했고, monotonic stack인 min_stack을 따로 만들어서 지금까지의 최솟값을 저장하는 방법을 고안했다.

무조건 min_stack 내부가 오름차순의 순서가 되도록 하고, min_stack의 top에 있는 값이 현재 스택에서의 최솟값인 것이다.

이를 위해

• push할때는 최솟값 갱신이 필요한 경우에만 min_stack에 push하도록 하고,(이때 최솟값과 같은 값이어도 min_stack에 push해야 추후 pop로직이 정상작동한다)
• pop할 때는 pop되는 값이 min_stack의 top에 있는 값과 같은 경우에만 min_stack에서도 pop을 하도록 했다.

class MinStack:

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

    def push(self, val: int) -> None:
        self.stack.append(val)

        # 현재 최솟값보다 큰 값이면 min_stack 업데이트 X
        if self.min_stack and self.min_stack[-1] < val:
            return

        self.min_stack.append(val)


    def pop(self) -> None:
        num = self.stack.pop()
        if self.min_stack[-1] == num: # 최솟값이었으면
            self.min_stack.pop()

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

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

discussion을 보니, 나는 stack과 min_stack의 원소수를 차이나게 뒀는데, 항상 같게 설정하는 코드도 있었다. 원소수를 항상 같게 두는게 좀 더 직관적이기는 한 것 같다.

class MinStack:

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

    def push(self, val: int) -> None:
        self.stack.append(val)

        if self.min_stack:
            val = min(self.min_stack[-1],val)
        self.min_stack.append(val)


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

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

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