Java all operations O(1) except popMax being O(n)


  • 0
    A
    class MaxStack {
    
        private Stack<Integer> primaryStack;
        private Stack<Integer> secondaryStack;
    
        /** initialize your data structure here. */
        public MaxStack() {
            primaryStack = new Stack<>();
            secondaryStack = new Stack<>();
        }
    
        public void push(final int x) {
            primaryStack.push(x);
            if (secondaryStack.isEmpty() || secondaryStack.peek() <= x) {
                secondaryStack.push(x);
            }
        }
    
        public int pop() {
            int popped = primaryStack.pop();
            if (secondaryStack.peek() == popped) {
                secondaryStack.pop();
            }
            return popped;
        }
    
        public int top() {
            return primaryStack.peek();
        }
    
        public int peekMax() {
            return secondaryStack.peek();
        }
    
        public int popMax() {
            int max = secondaryStack.pop();
            Stack<Integer> tempStack = new Stack<>();
            while (!primaryStack.isEmpty() && primaryStack.peek() != max) {
                tempStack.push(primaryStack.pop());
            }
    
            if (!primaryStack.isEmpty()) {
                primaryStack.pop();
    
                while (!tempStack.isEmpty()) {
                    push(tempStack.pop());
                }
            }
    
            return max;
        }
    }
    

Log in to reply
 

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