Min Stack

LeetCode 155. 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.

여러가지 방법이 있더라

getMin()을 호출할 때마다 최솟값 구하기

문제에서는 시간복잡도가 O(1)이 되는 것을 요구하고 있다.
이 방법은 getMin()이 O(n)이 되므로 요구에 맞지 않다.

minimum 속성을 두어 갱신하기

pop()을 할 때 최솟값을 다시 구해야 하므로 최악의 경우 pop()이 O(n)이 된다.

스택에 원소를 넣을 때 최솟값도 같이 넣기 가능

원소를 넣을 때 그 시점에서의 최솟값을 튜플 등으로 묶어 스택에 추가한다.
pop() 연산을 할 때 최솟값을 구할 수 있으며 push()의 경우 가장 위에 있는 항목에 저장된 최솟값을 참고하면 된다.

최솟값용 스택 따로 만들기 가능

세 번째와 유사하다.

코드

class MinStack:
    def __init__(self):
        self.stack = list()
        self.minimum = list()

    def push(self, val: int) -> None:
        if not self.minimum: self.minimum.append(val)
        else: self.minimum.append(min(self.minimum[-1], val))
        self.stack.append(val)

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

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

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