Java solution with 3 stacks.


  • 0
    L

    Passed all the test cases, but not sure whether it covers all.

    s1 stores all the values, s2 stores the max values, and s3 stores the values popped from s1 during the popMax() steps.

    class MaxStack {
        Stack<Integer> s1, s2, s3;
        /** initialize your data structure here. */
        public MaxStack() {
            s1 = new Stack<>();
            s2 = new Stack<>();
            s3 = new Stack<>();
        }
        
        public void push(int x) {
            s1.push(x);
            if (s2.isEmpty() || x >= s2.peek())
                s2.push(x);
        }
        
        public int pop() {
            int val = s1.pop();
            if (!s2.isEmpty() && s2.peek() == val)
                s2.pop();
            return val;
        }
        
        public int top() {
            return s1.peek();
        }
        
        public int peekMax() {
            if (s2.isEmpty())
                return s1.peek();
            return s2.peek();
        }
        
        public int popMax() {
            int max = !s2.isEmpty() ? s2.pop() : s1.peek();
            while (!s1.isEmpty() && s1.peek() != max)
                s3.push(s1.pop());
            
            s1.pop();
            while (!s3.isEmpty())
                push(s3.pop());
            return max;
        }
    }
    
    /**
     * Your MaxStack object will be instantiated and called as such:
     * MaxStack obj = new MaxStack();
     * obj.push(x);
     * int param_2 = obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.peekMax();
     * int param_5 = obj.popMax();
     */
    

  • 0
    M

    I don't think you need to check s2.isEmpty(), if this MaxStack class is used correctly (such as no pop() called on an empty stack)

    Below is my code, almost same as your idea.
    Time complexity:
    push(), pop(), top(), peekMax() - O(1)
    popMax() - O(n)
    Space complexity: O(n)

    class MaxStack {
        private final Stack<Integer> value;
        private final Stack<Integer> max;
        private final Stack<Integer> temp;
    
        public MaxStack() {
            value = new Stack<>();
            max = new Stack<>();
            temp = new Stack<>();
        }
        
        public void push(int x) {
            value.push(x);
            if (max.isEmpty() || x >= max.peek()) {
                max.push(x);
            }
        }
        
        public int pop() {
            int result = value.pop();
            if (max.peek() == result) {
                max.pop();
            }
            return result;
        }
        
        public int top() {
            return value.peek();
        }
        
        public int peekMax() {
            return max.peek();
        }
        
        public int popMax() {
            int result = peekMax();
            while (top() != result) {
                temp.push(pop());
            }
            pop();
            while (!temp.isEmpty()) {
                push(temp.pop());
            }
            return result;
        }
    }
    

  • 0
    M

    @Mark_89 Agelle


  • 0
    M

    @Mark_89 And also, you do not need to keep temp stack as class field, it could be just popMax method's temporary stack.


  • 0
    M

    @muma2
    Yes I agree with you.
    I just want to keep my code consistent with the title "Java solution with 3 stacks".
    :-P


  • 0
    R
    This post is deleted!

Log in to reply
 

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