Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • getMin() — Retrieve the minimum element in the stack.

Example:

  1. MinStack minStack = new MinStack();
  2. minStack.push(-2);
  3. minStack.push(0);
  4. minStack.push(-3);
  5. minStack.getMin();   --> Returns -3.
  6. minStack.pop();
  7. minStack.top();      --> Returns 0.
  8. minStack.getMin();   --> Returns -2.

Solution:

  1. class MinStack {
  2.   Stack<Integer> s1 = new Stack<>();
  3.   Stack<Integer[]> s2 = new Stack<>();
  5.   public void push(int x) {
  6.     s1.push(x);
  7.     if (s2.isEmpty() || x < s2.peek()[0]) {
  8.       s2.push(new Integer[]{x, 1});
  9.     } else if (x == s2.peek()[0]) {
  10.       s2.peek()[1]++;
  11.     }
  12.   }
  14.   public void pop() {
  15.     if (s1.peek().intValue() == s2.peek()[0]) {
  16.       s2.peek()[1]--;
  17.       if (s2.peek()[1] == 0)
  18.         s2.pop();
  19.     }
  20.     s1.pop();
  21.   }
  23.   public int top() {
  24.     return s1.peek();
  25.   }
  27.   public int getMin() {
  28.     return s2.peek()[0];
  29.   }
  30. }