Clear and simple Java solution with helper methods


  • 0
    W
    class MaxStack {
      Stack<Integer> st = new Stack();
      Stack<Integer> max = new Stack();
      /** initialize your data structure here. */
      public MaxStack() {
      }
    
      public void push(int x) {
        st.push(x);
        updateMaxStack(x);
      }
    
      public int pop() {
        int val = st.pop();
        if(max.peek() == val) max.pop();
        return val;
      }
    
      public int top() {
        return st.peek();
      }
    
      public int peekMax() {
        return max.peek();
      }
    
      public int popMax() {
        int maxVal = max.pop();
        removeFromStack(maxVal);
        return maxVal;
      }
    
      // Helper methods
    
      private void updateMaxStack(int x) {
        if(max.empty() || max.peek() <= x) max.push(x);
      }
    
      private void removeFromStack(int max) {
        Stack<Integer> aux = new Stack();
        // Pop all elements until max is found,
        // but saving them to auxiliary stack
        int cur = st.pop();
        while(cur != max) {
          aux.push(cur);
          cur = st.pop();
        }
        // Push all elements back to st and update max
        while(!aux.empty()) {
          st.push(aux.pop());
          updateMaxStack(st.peek());
        }
      }
    }
    

Log in to reply
 

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