[LeetCode] 155. Min Stack

https://leetcode.com/problems/min-stack

개요

1. 최소값을 반환하는 스택을 구현하기
   • input 코드 예시

   MinStack minStack = new MinStack();
   minStack.push(-2);
   minStack.push(0);
   minStack.push(-3);
   minStack.getMin(); // -3을 반환
   minStack.pop();
   minStack.top(); // 0을 반환
   minStack.getMin(); // -2를 반환

2. push() pop() top() getMin() 메소드를 가진 클래스 구현
   • 모든 메서드의 시간복잡도는 O(1)

문제 해결 아이디어

• 스택은 Last In First Out 이다.
  - 어떤 특정한 value가 push 될 때 스택 상태와, pop 될 때 스택 상태가 동일하다.
  
• 스택 내 최소값을 값이 push 될 때 추산할 수 있다.

🤨 최소값을 저장하는 Array를 추가로 구성하자

코드

public class MinStack {
    ArrayList<Integer> value;
    ArrayList<Integer> min;
    int top = -1;

    public MinStack() {
        value = new ArrayList<>();
        min = new ArrayList<>();
    }
    ...
}

• 스택의 값이 저장되는 ArrayList value와 [0:value] 범위일때 최소값을 저장하는 ArrayList min을 생성
• 스택의 가장 상위에 저장된 인덱스를 가르키는 top 변수 생성

public class MinStack {
   ...
    public void push(int val) {
        value.add(val);
        if (top != -1) min.add(Math.min(min.get(top), val));
        else min.add(val);
        top++;
    }

    public void pop() {
        value.remove(top);
        min.remove(top);
        top--;
    }
...

• 값이 push 될 때,
  • 값을 value 에 저장하고 top의 값을 1 증가시킴
  • 직전 인덱스의 min값과 현재 값을 비교해서 최소 값 저장
• 값이 pop 될 때,
  • top 인덱스의 값을 삭제하고, top의 값을 1 감소시킴
  • 해당 인덱스의 min 값도 함께 삭제

public class MinStack {
    ...
        public int top() {
        return value.get(top);
    }

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

• top()은 현재 가장 상위 값 반환
• getMin() 호출될 때마다 top 인덱스의 min값 반환

결과

전체 코드 github 링크

다른 풀이

class MinStack {
    LinkedList<TplusMin> stack;
    private class TplusMin {
        int val;
        int min;
        public TplusMin(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }

    public MinStack() {
        stack = new LinkedList<>();
    }
    
    public void push(int val) {
        int newMin;
        if (stack.size() == 0){
            newMin = val;
        }
        else {
            int currentMin = stack.getFirst().min;
            newMin = val < currentMin ? val : currentMin;
        }
        stack.addFirst(new TplusMin(val, newMin));
    }
    
    public void pop() {
        stack.removeFirst();
    }
    
    public int top() {
        return stack.peekFirst().val;
    }
    
    public int getMin() {
        return stack.peekFirst().min;
    }
}

나는 ArrayList를 두개 생성하는 방식이었는데, 이 풀이는 클래스를 생성하는 방식이었다.
java의 클래스 특성을 잘 활용한 풀이인것 같다.
그리고 LinkedList 의 구현체가 java 기본 유틸에 있다는 것을 처음 알았다.