[LeetCode] 155. Min Stack

Min Stack - LeetCode

Min값을 O(1)안에 반환하는 Stack을 구현하는 문제입니다.

 

Example 1:

["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

 

문제접근

ArrayList로 스택을 만들어 요구사항의 메서드를 모두 만족시켰습니다.

 

중요한 점은 Min값을 갖기위해 ArrayList에 Integer가 아닌 Integer[] 배열이 들어가고

0인덱스에 val, 1인덱스에 min값을 갱신해 주었습니다.

 

Push할때 Min값을 갱신하는것은 간단했지만, Pop하는 과정에서 stack의 사이즈체크를 해주는것이 포인트입니다.

 

 class MinStack {
   
    int top;
    int min;
    ArrayList<Integer[]> stack;

    public MinStack() {
        top = -1;
        min = Integer.MAX_VALUE;
        stack = new ArrayList<>();
    }

    public void push(int val) {
        min = Math.min(min, val);
        stack.add(new Integer[]{val, min});
        top++;
    }

    public void pop() {
        stack.remove(top--);
        if (stack.size() != 0)
            min = stack.get(top)[1];
        if (stack.size() == 0)
            min = Integer.MAX_VALUE;
    }

    public int top() {
        return stack.get(top)[0];
    }

    public int getMin() {
        return min;
    }

 

시간복잡도

구현한 함수 전부 O(1)안에 해결됩니다.

 

다른사람의 풀이

두개의 Stack을 사용해서 풀이하였습니다.

 

minStack과 Stack으로 나누어서 들어오는 데이터마다 Min값을 넣어주면 int[]을 사용안해도

요구사항을 해결할 수 있습니다.

 

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

    public MinStack() {
        minStack = new Stack<>();
        stack = new Stack<>();
    }
    
    public void push(int val) {
        int currentMin;
        
        if (minStack.isEmpty() || val <= (currentMin = minStack.peek()))
            minStack.push(val);
        else
            minStack.push(currentMin);

        stack.push(val);
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

 

느낀점

스택을 사용하는 방법은 Array, ArrayList, LinkedList, Stack 가있습니다.

각각 자료구조마다 Stack으로 구현했을때 장단점이 무었인지 잘 파악해야겠습니다.

 

참고

Min Stack - LeetCode