155 similar

popMax() seems a bit tricky. It should be O(N).

congr commented 5 years ago

class MaxStack {
    Stack<Integer> stk;
    Stack<Integer> max;

    /** initialize your data structure here. */
    public MaxStack() {
        stk = new Stack();    
        max = new Stack();
    }

    public void push(int x) {
        stk.push(x);
        if (max.isEmpty()) max.push(x);
        else max.push(Math.max(max.peek(), x));
    }

    public int pop() {
        max.pop();
        return stk.pop();
    }

    public int top() {
        return stk.peek();
    }

    public int peekMax() {
        return max.peek();
    }

    // O(N) - use other methods already implemented
    public int popMax() {
        Stack<Integer> tmp = new Stack();
        int max = peekMax();

        while(top() != max) tmp.push(pop()); // max, stk pop
        pop(); // !!!
        while(!tmp.isEmpty()) push(tmp.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();
 */

congr / world

LeetCode : 716. Max Stack #450

155 similar