Java accepted with one stack and one pq


  • 2
    X

    The code is very clear and short
    Using pq to get max while using stack to store data

    class MaxStack {

    Stack<Integer> s;
    PriorityQueue<Integer> pq;
    /** initialize your data structure here. */
    public MaxStack() {
        s = new Stack<Integer>();
        pq = new PriorityQueue<Integer>(10000, Collections.reverseOrder());
    }
    
    public void push(int x) {
        s.push(x);
        pq.offer(x);
    }
    
    public int pop() {
        int pop = s.pop();
        pq.remove(pop);
        return pop;
    }
    
    public int top() {
        return s.peek();
    }
    
    public int peekMax() {
        return pq.peek();
    }
    
    public int popMax() {
        int max = pq.poll();
        Stack<Integer> sp = new Stack<Integer>();
        while (!s.isEmpty()) {
            if (s.peek() != max) {
                sp.push(s.pop());
            } else {
                s.pop();
                break;
            }
        }
        while (!sp.isEmpty()) {
            s.push(sp.pop());
        }
        return max;
    }
    

    }


  • 0
    E

    Smart solution!


  • 0
    F

    Using two stack

    class MaxStack {
    
        Stack<Integer> s1;
        Stack<Integer> s2;
        int max;
        /** initialize your data structure here. */
        public MaxStack() {
            s1 = new Stack<>();
            s2 = new Stack<>();
            max = Integer.MIN_VALUE;
        }
        
        public void push(int x) {
            if (x >= max) {
                s1.push(max);
                max = x;
            }
            s1.push(x);
        }
        
        public int pop() {
            int res = s1.pop();
            if (res == max) {
               max = s1.pop();
            }
            return res;
        }
        
        public int top() {
            return s1.peek();
        }
        
        public int peekMax() {
            return max;
        }
        
        public int popMax() {
            while (s1.peek() != max) {
                s2.push(s1.pop());
            }
            int res = s1.pop();
            max = s1.pop();
            while (!s2.isEmpty()) {
                int val = s2.pop();
                if (val >= max) {
                    s1.push(max);
                    max = val;
                }
                s1.push(val);
            }
            return res;
        }
    }
    

Log in to reply
 

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