Leetcode MinStack JAVA

이 문제는 단순하게 생각하면 스택을 구현해서 Min 값을 구할 때 매번 O(N)의 복잡도로 값을 구하는 생각을 할 수 있다.

하지만, 그렇게 하는 방법보다 더 간단한 방법이 있다.

Stack을 만들어서 더 작은 값이 나올때마다 이전의 min값을 미리 stack에 쌓아놓고 pop을 할 떄 그 다음에 있는 숫자를 min으로 업데이트 한다.

만약 pop할때 min값이 아니었다면 단순히 pop만을 한다.

이를 통해서 Min 값을 구할 떄의 시간복잡도는 O(1)로 줄어들게 된다.

class MinStack {
    int min;
    Deque<Integer> deque;

    /** initialize your data structure here. */
    public MinStack() {
        deque = new ArrayDeque<>();
        min = Integer.MAX_VALUE;
    }

    public void push(int x) {
        if(x<=min){
            deque.push(min);
            min=x;
        }
        deque.push(x);
    }

    public void pop() {
        if(deque.pop()==min)
            min=deque.pop();
    }

    public int top() {
        return deque.getFirst();
    }

    public int getMin() {
        return min;
    }
}