155. Min Stack

https://leetcode.com/problems/min-stack/

Min Stack - LeetCode

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(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.

 

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

 

Constraints:

• -231 <= val <= 231 - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 104 calls will be made to push, pop, top, and getMin.

 

Solution

import heapq

class MinStack:
    def __init__(self):
        self.stack = []
        self.heap = []

    def push(self, val):
        self.stack.append(val)
        heapq.heappush(self.heap, val)

    def pop(self):
        if self.heap[0] == self.stack[-1]:
            self.stack.pop()
            heapq.heappop(self.heap)
        else:
            self.heap.remove(self.stack.pop())

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

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

• heapq 를 사용하여, 스택에서의 최소값을 언제든 뽑을 수 있도록 하였다.
• 하지만 같은 내용을 담은 리스트를 2개를 사용하기 때문에, 메모리를 2배 사용한다.

 

another 1

class MinStack:

    def __init__(self):
        self.stack = [(-1, float('inf'))]

    def push(self, x):
        self.stack.append([x, min(x, self.stack[-1][1])])

    def pop(self):
        self.stack.pop()

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

    def getMin(self):
        return self.stack[-1][1]

• push를 통해 수를 넣을 때, 그때까지의 가장 작을 수를 함께 묶어서 넣는다. (num, min num)
• 그래서 하나의 stack만 사용하여 메모리를 절약한다.
• 첫 push할 때 비교대상이 없으므로, __init__ 에서 임의의 한 값을 넣어준다.

 

우선순위 큐 heapq, priorityqueue

import heapq
heap = []
heapq.heappush(heap, 1)
heapq.heappop(heap) # heap[0]을 보여주고 삭제한다.

from queue import PriorityQueue
pq = PriorityQueue()
pq.put(1)
pq.get()

heap 구조를 가지고, 원소들이 항상 정렬된 상태로 추가되고 삭제된다.

 

 

queue.PriorityQueue()는 heapq를 기반으로 만들어졌고 thread safe 한 대신 속도가 느리다.

 

쓰레드 세이프를 지원하지 않으면 예를 들어 1번 쓰레드의 값이 2번 쓰레드에 의해 변경될 수 있어 문제가 발생할 수 있다. 하지만 파이썬은 GIL의 특성상 멀티 쓰레딩이 거의 의미가 없어 대부분 멀티 프로세싱을 활용한다. 따라서 PriorityQueue 모듈의 멀티 쓰레딩 지원은 사실 큰 의미가 없다. 또한 쓰레드 세이프를 보장한다는 얘기는 내부적으로 락킹(Locking)을 제공한다는 의미이므로 락킹(Locking Overhead)가 발생해 영향을 끼친다. 따라서 굳이 멀티 쓰레드로 구현할 게 아니면 PriorityQueue 모듈은 사용할 필요가 없고 실무에서도 대부분 heapq로 구현하고 있다.