[ Top Interview 150 ] 155. Min Stack

문제

155. Min Stack

 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.

• 구현 해야할 기능

  • MinStack : Stack 기능을 하면서 Stack 안의 최소값을 반환할 수 있는 Stack 구현
  • void push(int val) : val 값을 넣기
  • void pop() : 가장 최근에 넣은 값을 제거
  • int top() : 가장 최근에 넣은 값을 반환
  • int getMin() : MinStack 안의 최소값 반환

• Condition

  • 모든 기능은 O(1) time complexity를 가져야 함

• 기본 제공 코드

  class MinStack {
  
      public MinStack() {
  
      }
  
      public void push(int val) {
  
      }
  
      public void pop() {
  
      }
  
      public int top() {
  
      }
  
      public int getMin() {
  
      }
  }

구현 전략

• 기본 구현 전략

  • push(int val), pop(), top() 은 기존 Stack을 이용하여 구현이 가능
  • 목표는 getMin()을 time complexity O(1)으로 구현하는 것이 목표
  • getMin() 구현 방법 : 내 하위의 element 중에서의 최소값을 가지는 Stack(subMin)을 만듦, subMin의 가장 위에 있는 값은 전체 element의 최소값을 나타내게 된다.

• 구현 방법

  • Java 에서 제공하는 라이브러리를 최대한 이용한다면, Stack을 이용해서 구현할 수 있다.
  • Java 에서 제공하는 라이브러리를 최대한 이용하지 않는다면 배열을 이용해서 구현할 수 있다.

• Complexity

  • Time complexity : O(n)
  • Space complexity: O(n)

1차 답안 (Java 라이브러리 Stack 이용)

public class MinStack {

    private final Stack<Integer> values;
    private final Stack<Integer> subMin;

    public MinStack() {
        this.values = new Stack<>();
        this.subMin = new Stack<>();
    }

    public void push(int val) {
        if (values.isEmpty()) {
            values.add(val);
            subMin.add(val);
            return;
        }

        values.add(val);
        subMin.add(Math.min(subMin.peek(), val));
    }

    public void pop() {
        values.pop();
        subMin.pop();
    }

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

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

2차 답안 (Java 라이브러리 List 이용)

class MinStack {

    private final List<Integer> values;
    private final List<Integer> mins;
    private int topIndex;

    public MinStack() {
        this.values = new LinkedList<>();
        this.mins = new LinkedList<>();
        this.topIndex = -1;
    }

    public void push(int val) {
        if (topIndex == -1) {
            values.add(val);
            mins.add(val);
            topIndex++;
            return;
        }

        values.add(val);
        mins.add(Math.min(mins.get(topIndex), val));
        topIndex++;
    }

    public void pop() {
        values.remove(topIndex);
        mins.remove(topIndex);
        topIndex--;
    }

    public int top() {
        return values.get(topIndex);
    }

    public int getMin() {
        return mins.get(topIndex);
    }
}

3차 답안 (Array 이용)

public class MinStack {

	private static final int DEFAULT_SIZE = 32;

    private int[] values;
    private int[] subMin;
    private int topIndex;

    public MinStack() {
        this.values = new int[DEFAULT_SIZE];
        this.subMin = new int[DEFAULT_SIZE];
        this.topIndex = -1;
    }

    public void push(int val) {
        
        if (topIndex + 1 >= values.length) {
            values = copyAndSizeDouble(values);
            subMin = copyAndSizeDouble(subMin);
        }
        
        topIndex++;
        values[topIndex] = val;
        
        if (topIndex == 0) {
            subMin[topIndex] = val;
            return;
        }
        subMin[topIndex] = Math.min(val, subMin[topIndex - 1]);
    }

    public void pop() {
        values[topIndex] = 0;
        subMin[topIndex] = 0;
        topIndex--;
    }

    public int top() {
        return values[topIndex];
    }

    public int getMin() {
        return subMin[topIndex];
    }

    private int[] copyAndSizeDouble(int[] array) {
        int[] newArray = new int[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            newArray[i] = array[i];
        }
        return newArray;
    }
}