Accepted clean Java solution (two stacks, space efficient)


  • 0

    We use the 1st stack to store the data and use the 2nd stack to keep tracking the minimum value. But rather than keep adding the same minimum value to the 2nd stack, we can let the 2nd stack store an array {data, count}. We just update the count when the new data equals to the current minimum value.

    Example, let's push the following data to our min stack: {512, -1024, -1024, 512}, the two stacks will look like this:

        512
      -1024
      -1024       -1024(2)
        512         512(1)   
    -----------  -----------
        s1           s2
    

    Code:

    public class MinStack {
      Stack<Integer> s1 = new Stack<Integer>();
      Stack<Integer[]> s2 = new Stack<Integer[]>();
    
      public void push(int x) {
        s1.push(x);
        
        if (s2.isEmpty() || x < s2.peek()[0])
            s2.push(new Integer[]{x, 1});
            
        else if (s2.peek()[0] == x)
            s2.peek()[1]++;  // update the count
      }
    
      public void pop() {
        if (s1.peek().intValue() == s2.peek()[0]) {
            if (s2.peek()[1] > 1)
                s2.peek()[1]--; // update the count
            else
                s2.pop();
        }
        
        s1.pop();
      }
    
      public int top() {
        return s1.peek();
      }
    
      public int getMin() {
        return s2.peek()[0];
      }
      
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.