[LeetCode/Java] 155. Min Stack

0. 문제

https://leetcode.com/problems/min-stack/?envType=study-plan-v2&envId=top-interview-150

1. 문제 설명

• 최소값을 반환하는 메서드가 있는 Stack을 구현하라

2. 문제 풀이

2.1. 접근법 : PriorityQueue 사용

• PriorityQueue는 삽입 시에 O(logN)의 시간 복잡도가 걸리고, 최소값 조회도 가장 앞에 있는 원소를 꺼내면 되기 때문에 O(1)의 시간 복잡도가 소요된다.
• push 메서드가 호출되면 PriorityQueue에도 값을 저장한다.
• pop 메서드가 호출되면 Stack과 함께 PriorityQueue에서도 Stack에서 pop한 값을 삭제한다.

3. 코드

class MinStack {
    List<Integer> stack;
    PriorityQueue<Integer> q;

    public MinStack() {
        stack = new ArrayList();
        q = new PriorityQueue();
    }
    
    public void push(int val) {
        q.add(val);
        stack.add(val);
    }
    
    public void pop() {
        int val = stack.get(stack.size() - 1);
        stack.remove(stack.size() - 1);
        q.remove(val);
    }
    
    public int top() {
        return stack.get(stack.size() - 1);
    }
    
    public int getMin() {
        return q.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

4. 결과