716. Max Stack #

题目 #

设计一个最大栈数据结构，既支持栈操作，又支持查找栈中最大元素。

实现 MaxStack 类：

MaxStack() 初始化栈对象
void push(int x) 将元素 x 压入栈中
int pop() 移除栈顶元素并返回这个元素
int top() 返回栈顶元素，无需移除
int peekMax() 检索并返回栈中最大元素，无需移除
int popMax() 检索并返回栈中最大元素，并将其移除。如果有多个最大元素，移除 最靠近栈顶 的那个

思路 #

Explicit Better Than Implicit

代码 #

class MaxStack {
    private class ListNode implements Comparable<ListNode> {
        public int index;
        
        public int val;
        public ListNode prev;
        public ListNode next;
        
        ListNode(int index, int val, ListNode prev, ListNode next) {
            this.index = index;
            this.val = val;
            this.prev = prev;
            this.next = next;
        }
        
        public int compareTo(ListNode other) {
            if (this.val == other.val) return other.index - this.index;
            return other.val - this.val;
        }
    }
    
    private ListNode sentinel;
    private PriorityQueue<ListNode> queue;
    private int index;
    
    public MaxStack() {
        this.sentinel = new ListNode(-1, -1, null, null);
        this.sentinel.prev = this.sentinel.next = this.sentinel;
        this.queue = new PriorityQueue<>();
        this.index = 0;
    }
    
    public void push(int x) {
        this.index += 1;
        this.sentinel.next = new ListNode(this.index, x, this.sentinel, this.sentinel.next);
        this.sentinel.next.next.prev = this.sentinel.next;
        this.queue.offer(this.sentinel.next);
    }
    
    public int pop() {
        int result = this.sentinel.next.val;
        this.queue.remove(this.sentinel.next);
        this.sentinel.next = this.sentinel.next.next;
        this.sentinel.next.prev = this.sentinel;
        return result;
    }
    
    public int top() {
        return this.sentinel.next.val;
    }
    
    public int peekMax() {
        return this.queue.peek().val;
    }
    
    public int popMax() {
        ListNode ptr = this.queue.poll();
        ptr.prev.next = ptr.next;
        ptr.next.prev = ptr.prev;
        
        return ptr.val;
    }
}