LeetCode 155 - Min Stack

Min Stack - LeetCode

 

stack을 구현하는 문제이다. 모든 작업이 O(1)의 시간복잡도로 가능해야 한다.

 

대부분의 기능은 stack을 쓰면 O(1)이 가능하지만 최솟값을 알아내야 하는 기능도 O(1)로 동작해야 한다는 점이 중요하다.

우선 최소값을 변수로 저장하는 방법을 생각해 보자.

이 방법은 최솟값을 바로 찾을 수는 있지만 최솟값이 갱신될 때 스택 내의 모든 요소를 순회해야 한다.

별도로 해당 레벨에서의 최솟값을 가지고 있어야 할 객체가 필요하다.

즉 삽입되는 값을 노드라고 생각했을 때 항상 노드 기준 최소값을 함께 기억하고 있는 것이다.

class MinStack {

    static class Node {
        int val;
        int min;

        public Node(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }

    private Deque<Node> stack = new LinkedList<>();

    public MinStack() {
    }
    
    public void push(int val) {
        if (!stack.isEmpty()) {
            Node top = stack.peekLast();
            stack.addLast(new Node(val, Math.min(val, top.min)));
            return;
        }
        stack.addLast(new Node(val, val));
    }
    
    public void pop() {
        stack.pollLast();
    }
    
    public int top() {
        return stack.peekLast().val;
    }
    
    public int getMin() {
        return stack.peekLast().min;
    }
}

/**
 * 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();
 */