[LeetCode] 155. Min Stack - Java

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

You must implement a solution with O(1) time complexity for each function.

 

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.

 

push, pop top, 최소값을 구하는 기능을 constant time에 동작하는 Stack을 구현하는 문제이다.

 

---

 

내 풀이

 

첫 번째 풀이

class MinStack {
    private List<Integer> list; 

    public MinStack() {
        list = new ArrayList<>(); 
    }

    public void push(int val) {
        list.add(val);
    }

    public void pop() {
        list.remove(list.size() -1);
    }

    public int top() {
        return list.get(list.size() -1);
    }

    public int getMin() {
        int min = Integer.MAX_VALUE;
        for(Integer i : list){
            min = Math.min(min, i);
        }
        return 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();
 */

 

간단하게 ArrayList를 사용해서 구현해보았다. 문제는 getMin() 메서드이다

push, pop, top 메서드는 O(1)의 시간복잡도를 가지지만 getMin은 리스트 내에 모든 요소를 순회하며 최소값을 찾기 때문에 O(n)의 시간복잡도를 가진다.

공간복잡도는 공통적으로 O(n)이다.

실제 동작 속도를 봐도 5%의 효율로 측정되고 매우 비효율적이라는 것을 알 수 있다.

개선이 필요하다

 

 

두 번째 풀이

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if(minStack.size() == 0) minStack.push(val);
        else minStack.push(Math.min(val, minStack.peek()));
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

스택을 구현하는데 스택을 써도 되나 싶었지만 일단 해보았다.

getMin() 메소드를 구현하기 위해 스택을 2개 사용했다. 이렇게 하면 getMin() 도 시간복잡도가 O(1)로 줄어든다.

실제 동작속도에서도 효율이 크게 개선되었다.

근데 문제의 의도는 스택을 사용하여 푸는 방식이 아닌것 같아서 다른 풀이를 찾아보았다.

 

---

 

다른 사람의 풀이

class MinStack {
    ListNode top;

    public class ListNode{
        int data;
        int min;
        ListNode next;

        ListNode(int data) {
            this.data = data;
            next = null;
            min = Integer.MAX_VALUE;
        }
    }

    public MinStack() {
        top = null;
    }

    public void push(int val) {
        ListNode t = new ListNode(val);
        t.next = top;

        if(t.data < t.min) t.min = t.data;
        else t.min = top.min;

        top = t;
    }

    public void pop() {
        top = top.next;
    }

    public int top() {
        return top.data;
    }

    public int getMin() {
        return top.min;
    }
}

앞에서 푼 문제들과 같이 ListNode 라는 클래스를 통해서 다음 노드를 가리키는 포인터를 저장하는 방식이다.

 

• push : 새 노드를 생성하여 스택의 맨 위에 추가하고 min 값을 업데이트 한다
• pop : 맨 위의 노드를 제거한다
• top : 맨 위 노드의 데이터를 반환한다.
• getMin : 맨 위 노드의 min 값을 반환한다.

 

push 할 때 해당 노드에 매번 최소값을 업데이트 해주기 때문에 getMin 에서 별다른 연산 없이 바로 최소값을 반환해줄 수 있다.

시간복잡도도 O(1)로 유지된다.