自我感动的剖析

题目

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

实现 MaxStack 类：

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

示例：

输入
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
输出
[null, null, null, null, 5, 5, 1, 5, 1, 5]

解释
MaxStack stk = new MaxStack();
stk.push(5);   // [5] - 5 既是栈顶元素，也是最大元素
stk.push(1);   // [5, 1] - 栈顶元素是 1，最大元素是 5
stk.push(5);   // [5, 1, 5] - 5 既是栈顶元素，也是最大元素
stk.top();     // 返回 5，[5, 1, 5] - 栈没有改变
stk.popMax();  // 返回 5，[5, 1] - 栈发生改变，栈顶元素不再是最大元素
stk.top();     // 返回 1，[5, 1] - 栈没有改变
stk.peekMax(); // 返回 5，[5, 1] - 栈没有改变
stk.pop();     // 返回 1，[5] - 此操作后，5 既是栈顶元素，也是最大元素
stk.top();     // 返回 5，[5] - 栈没有改变

提示：

• $-10^7 <= x <= 10^7$
• 最多调用 104 次 push、pop、top、peekMax 和 popMax
• 调用 pop、top、peekMax 或 popMax 时，栈中 至少存在一个元素

**进阶： **

试着设计解决方案：调用 top 方法的时间复杂度为 $O(1)$ ，调用其他方法的时间复杂度为 $O(logn)$。

分析

1、记录最大值节点的上下文位置
2、维护一个优先队列，从大到小记录给个节点
3、使用最大堆

栈+优先队列

    class MaxStack {
        PriorityQueue<Node> p;
        Node head;
        Node tail;
        int idx;

        public MaxStack() {
            p = new PriorityQueue<>((o1, o2) -> (o2.v == o1.v ? o2.idx - o1.idx : o2.v - o1.v));
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.pre = head;
            idx = 0;
        }

        public void push(int x) {
            Node next = head.next;
            Node node = new Node(x, idx++);
            head.next = node;
            node.pre = head;
            node.next = next;
            next.pre = node;
            p.offer(node);
        }

        public int pop() {
            Node node = head.next;
            Node next = node.next;
            head.next = next;
            next.pre = head;
            node.pre = node.next = null;
            return node.v;
        }

        public int top() {
            return head.next.v;
        }

        public int peekMax() {
            while (!p.isEmpty()&&p.peek().pre == null && p.peek().next == null) p.poll();
            return p.peek().v;
        }

        public int popMax() {
            peekMax();
            Node node = p.poll();
            Node pre = node.pre;
            Node suf = node.next;
            pre.next = suf;
            suf.pre = pre;
            return node.v;
        }

        class Node {
            int v;
            int idx;
            Node pre;
            Node next;

            public Node(int x, int idx) {
                this.v = x;
                this.idx = idx;
            }

            public Node() {
            }
        }
    }

/**
 * 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();
 */

最大堆

class MaxStack {

    private TreeSet<int[]> stack;
    private TreeSet<int[]> values;
    private int cnt;

    public MaxStack() {
        Comparator<int[]> comp = (a, b) -> {
            return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
        };
        stack = new TreeSet<>(comp);
        values = new TreeSet<>(comp);
        cnt = 0;
    }

    public void push(int x) {
        stack.add(new int[] { cnt, x });
        values.add(new int[] { x, cnt });
        cnt++;
    }

    public int pop() {
        int[] pair = stack.pollLast();
        values.remove(new int[] { pair[1], pair[0] });
        return pair[1];
    }

    public int top() {
        return stack.last()[1];
    }

    public int peekMax() {
        return values.last()[0];
    }

    public int popMax() {
        int[] pair = values.pollLast();
        stack.remove(new int[] { pair[1], pair[0] });
        return pair[0];
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com