Leetcode: Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
 

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Stack의 기본적인 메소드들 + min element를 알아내는 메소드들이 모두 O(1)에 동작할 수 있도록 구현하는 문제이다.

처음에는 기본적으로 사용될 stack + min을 구하기 위한 추가적인 자료구조를 이용하여 구현하려 하였으나, stack하나로도 구현이 가능하여 아래와 같이 구현하였다. 

 

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_val = float('inf')

    def push(self, x: int) -> None:
        if x <= self.min_val:
            self.stack.append(self.min_val)
            self.min_val = x

        self.stack.append(x)

    def pop(self) -> None:
        x = self.stack.pop()
        if x == self.min_val:
            self.min_val = self.stack.pop()

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

    def getMin(self) -> int:
        return self.min_val

stack으로 사용하기 위한 리스트 하나와, 현재의 최솟값을 저장하는 변수를 선언해둔다. 

최솟값을 구하기 위한 방법은 여러가지가 있겠으나, 고민이 되었던 부분은 최솟값이 pop되었을 때 다음 최솟값이 무엇인지를 알아내는 것이었다. 입력된 숫자들을 정렬된 상태로 가지고 있고자 하면, O(1)에 구현할 수가 없었다. 

그래서 고민 그대로 크기순으로 정렬된 숫자들을 가지고 있는 것이 아니라, 현재의 최솟값 + 현재의 최솟값이 pop되었을 때의 다음 값만 알아낼 수 있으면 된다. 그 방법은 push할 때에 새로 들어온 값이 현재의 최솟값보다 작다면 (최솟값이 갱신이 되어야 한다면) 새로 들어온 값을 스택에 넣고 최솟값을 갱신하기 전에 현재의 최솟값을 스택에 넣어두는 것이다. 그렇다면 스택에서 pop된 값이 현재의 최솟값이라면, 한 번 더 pop을 한 값이 그 다음의 최솟값이 된다.

이 로직은 새로 들어온 값이 현재의 최솟값과 동일할 때도 수행되어야 하는데, 이는 현재의 최솟값은 스택에 여러 번 존재할 수 있기 때문이다. 예를 들어 0 -> 2 -> 0 의 순서로 값이 들어온 경우, min_val은 0이 된다. 두 번째 0이 들어올 때 기존의 min_val인 0을 push하지 않은 경우, 이 상태에서 pop을 하면 나오는 0은 최솟값과 동일하기 때문에 이 때에 또 pop을 하여 2를 최솟값으로 세팅하면 옳지 않은 결과가 나온다. 

 

링크: leetcode.com/problems/min-stack/

Min Stack - LeetCode