[Leetcode] 155. Min Stack

문제 바로가기

min-heap

Time Complexity:

• push: $O(\log n)$
• pop: $O(n)$
• top, getMin: $O(1)$

Space Complexity: $O(n)$

class MinStack:
    import heapq
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = list()
        self.heap = list()

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

    def pop(self) -> None:
        self.stack.pop()
        self.heap = self.stack[:]
        heapq.heapify(self.heap)

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

    def getMin(self) -> int:
        return self.heap[0]


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

dynamic programming

매 push마다 이전 min값과 현재 값을 비교한 새로운 min값을 같이 저장한다. 이를 통해 pop을 수행하더라도 이전 element에서의 min 값을 추가적인 계산없이 확인할 수 있다.
Time Complexity: $O(1)$
Space Complexity: $O(n)$

class MinStack:
    import heapq
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack: List[List[int,int]] = list()

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

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

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

    def getMin(self) -> int:
        return self.stack[-1][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()