[LeetCode] 155. Min Stack

Problem

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:

• -2^31 <= val <= 2^31 - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

---

Solution

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;
    public MinStack() {
        this.stack = new Stack<>();
        this.minStack = new Stack<>();
    }
    public void push(int val) {
        if (minStack.empty())
            minStack.push(val);
        else
            if (val <= minStack.peek())
                minStack.push(val);
        stack.push(val);
    }
    public void pop() {
        if (stack.pop().compareTo(minStack.peek()) == 0)
            minStack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return minStack.peek();
    }
}

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

Explanation

• 문제에서 구현해야 하는 MinStack과 기존 Stack의 차이점은 자료구조 내에 존재하는 최소값을 추적해야 하는 것이다. 그 외에는 차이점이 없으므로 Stack 참조변수를 선언하고, 생성자 내에서 새로운 Stack를 할당해준다.

  Stack<Integer> stack;
  public MinStack() {
    this.stack = new Stack<>();
  }
  

• MinStack 내에서 최소값을 추적하려면 MinStack이 생성된 이후에 들어오는 값을 조사하여 해당 값이 최소값이라면 메모를 해놓는 것이다.
• 그리고 MinStack에서 최소값이었던 값이 삭제되면 그 이전의 최소값이 새로운 최소값이 되므로 최소값으로 판단되었던 모든 값을 기록해놓아야 한다.
• 위의 조건을 만족시키기 위해서 최소 값을 추적하기 위한 Stack 참조변수를 선언하고, 생성자 내에 새로운 Stack을 할당해준다.

  Stack<Integer> minStack;
  public MinStack() {
    this.minStack = new Stack<>();
  }
  

• 추가하려는 값이 최소 값이면 stack뿐만 아니라 minStack에도 값이 추가되도록 한다.

  public void push(int val) {
    if (minStack.empty())
        minStack.push(val);
    else
        if (val <= minStack.peek())
            minStack.push(val);
    stack.push(val);
  }
  

• 값을 제거할 때는 제거하고자 하는 값이 최소 값이라면 minStack에 있는 값도 함께 삭제되도록 한다.

  public void pop() {
    if (stack.pop().compareTo(minStack.peek()) == 0)
        minStack.pop();
  }
  

• stack의 최상단 값을 조회할 때는 minStack을 건드릴 필요 없이 stack에 있는 값을 조회하도록 한다.

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

• stack의 최소값을 조회하려면 minStack의 최상단 값을 조회하도록 한다.

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