Min_Stack.md

Min Stack

Alias

• 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.

Note

• Main difference comparing to Max Stack is you don't need to remove the minimum value from stack.

Solutions

• Solution 1: 2 stacks

  • Idea
    • Use one stack as a normal stack, use another stack to remember the minimum value when inserting the corresonding value.
  

  class MinStack {
      Stack<Integer> stk = new Stack<>();
      Stack<Integer> minStk = new Stack<>();
  
      public MinStack() {
        
      }
    
      public void push(int val) {
          stk.push(val);
  
          // check if new val is the new minimum value 
          // comparing to the current minumum value (top of minStk)
          if (minStk.isEmpty() || val <= minStk.peek()) {
              minStk.push(val);
          } else {
              minStk.push(minStk.peek());
          }
      }
    
      public void pop() {
          stk.pop();
          minStk.pop();
      }
    
      public int top() {
          return stk.peek();
      }
    
      public int getMin() {
          return minStk.peek();
      }
  }