[DSA][Stack] 02. Min Stack

LeetCode 155

 

02. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.

 

 

[질문하기]

- Stack이 비어있을 때 pop(), top(), getMin() 등이 호출될 수 있나요? 그때는 어떻게 해야 하나요?

 

 

[아이디어]

- 현재의 값과 그 때까지의 최솟값을 함께 저장하자.

- 값이 아닌 상태만 저장하자

 

 

[풀이 1] Stack

class MinStack:
    def __init__(self):
        self.cur_stack = []
        self.min_stack = [float('inf')]

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

        if val < self.min_stack[-1]:
            self.min_stack.append(val)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> None:
        if not self.min_stack:
            return
        self.cur_stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.cur_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()

가장 단순하면서도 효율적인 방법은, 추가 스택(min_stack)을 하나 더 만들어서, 매 원소가 스택에 들어올 때 그 시점까지의 최소값을 함께 저장하는 것이다. 이렇게 하면 나중에 pop을 하더라도, 이전까지의 최솟값이 min_stack에 저장되어 있기 때문에 getMin() 연산을 O(1)로 처리할 수 있다.

 

⏱️ 시간복잡도

모든 operation을 O(1)에 처리할 수 있다.

🧠 공간복잡도

두 stack에 최대 원소의 개수만큼의 공간이 필요하므로 공간 복잡도는 O(n)이다.

 

 

[풀이 2] Stack

class MinStack:
    def __init__(self):
        self.min = float('inf')
        self.stack = []

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append(0)
            self.min = val
        else:
            self.stack.append(val - self.min)
            if val < self.min:
                self.min = val

    def pop(self) -> None:
        if not self.stack:
            return

        pop = self.stack.pop()
        if pop < 0:
            self.min = self.min - pop

    def top(self) -> int:
        top = self.stack[-1]
        if top > 0:
            return top + self.min
        else:
            return self.min

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


# 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()

1번 풀이에서 추가 공간 min_stack을 사용하지 않는 방법은 없을까?

getMin을 이용하면 cur_min 값을 알 수 있다. 여기서 우리가 생각해야 할 것은 cur_stack에 어떤 값을 저장해야 min_stack에 원소를 추가로 저장하지 않고도 old_min들을 알 수 있냐?는 것이다.

우리는 push된 원소의 value가 cur_min보다 클 때는 cur_min이 바뀌지 않기 때문에 관심이 없다. value가 cur_min보다 작은 값이 들어올 때만 관심이 있고 value가 cur_min이 되고 cur_min이 old_min이 됨을 안다. 그렇다면 어떤 값을 저장해야 min이 바뀌었는지 + old_min이 무엇인지 알 수 있을까?

바로 push된 원소의 value - old_min 값을 저장하면 된다. 이 값이 음수라면 우리는 이 시점에서 cur_min보다 작은 값이 들어왔음을 알 수 있고, value = cur_min이 되기 때문에 (value - old_min)의 값에서 cur_min을 빼면 -old_min을 알 수 있게 된다.

ex) 5 → 3이 들어왔을 때

cur_min이 5이므로 3 - 5 = -2를 저장하고, cur_min이 3으로 바뀐다.

나중에 원소를 봤을 때 -2 < 0이기 때문에 '이 시점에서 min이 바뀌었구나'를 알 수 있고, -2 - cur_min = -5이므로 old_min이 5였음 또한 알 수 있다.

 

⏱️ 시간복잡도

모든 operation을 O(1)에 처리할 수 있다.

🧠 공간복잡도

cur_stack만큼의 stack 공간이 필요하기 때문에 O(n)이지만 1번 풀이보다는 공간을 효율적으로 사용함을 알 수 있다.