鹅厂员工吐槽：毕业5年，感觉码农的路愈发难走，刚进公司拿2万感觉很轻松，买了房之后，现在拼命还很慌！

面试题：最大栈

popMax() 一加，原来的 Stack<Integer> 基本就废了。

我见过有人这么写：每次要最大值，就把栈扫一遍。测试数据十几个元素，看不出问题；线上一批任务压进来，接口耗时突然抖一下，日志里全是这种东西：

cost=183ms, action=popMax, stackSize=48291
cost=211ms, action=popMax, stackSize=53120

这种实现我第一眼就不太信。

最大栈要解决的不是“怎么找到最大值”这么简单，而是这几个操作都得稳：

push(x)
pop()
top()
peekMax()
popMax()

普通栈只关心栈顶。

最大栈还要随时知道当前最大值，甚至能把“最靠近栈顶的最大值”删掉。

这里容易写错的地方在 popMax()。比如栈里是：

5, 1, 5, 3

栈顶在右边。

popMax() 应该删掉后面那个 5，不是前面那个。这个细节不处理，很多题目能过一半，然后在重复最大值上翻车。

我一般不会用一个栈硬搞。

比较顺手的写法是：一个双向链表维护真实入栈顺序，一个 TreeMap 维护值到节点集合的映射。

双向链表负责：

push / pop / top

TreeMap 负责：

peekMax / popMax

因为 TreeMap.lastKey() 可以直接拿到当前最大值。

关键是，popMax() 找到最大值后，还要能从链表中间把那个节点摘掉。所以节点必须是双向的，不能只存值。

代码我写成下面这样，没放什么教学 demo，都是关键逻辑：

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.TreeMap;

publicclassMaxStack{

privatestaticclassNode{
int val;
        Node prev;
        Node next;

        Node(int val) {
this.val = val;
        }
    }

privatefinal Node head = new Node(0);
privatefinal Node tail = new Node(0);

privatefinal TreeMap<Integer, Deque<Node>> valueIndex = new TreeMap<>();

publicMaxStack(){
        head.next = tail;
        tail.prev = head;
    }

publicvoidpush(int x){
        Node node = new Node(x);
        linkBeforeTail(node);

        valueIndex.computeIfAbsent(x, k -> new ArrayDeque<>()).addLast(node);
    }

publicintpop(){
        Node node = tail.prev;
if (node == head) {
thrownew IllegalStateException("stack is empty");
        }

        unlink(node);

        Deque<Node> bucket = valueIndex.get(node.val);
        bucket.removeLast();
if (bucket.isEmpty()) {
            valueIndex.remove(node.val);
        }

return node.val;
    }

publicinttop(){
if (tail.prev == head) {
thrownew IllegalStateException("stack is empty");
        }
return tail.prev.val;
    }

publicintpeekMax(){
if (valueIndex.isEmpty()) {
thrownew IllegalStateException("stack is empty");
        }
return valueIndex.lastKey();
    }

publicintpopMax(){
if (valueIndex.isEmpty()) {
thrownew IllegalStateException("stack is empty");
        }

int max = valueIndex.lastKey();
        Deque<Node> bucket = valueIndex.get(max);

        Node node = bucket.removeLast();
        unlink(node);

if (bucket.isEmpty()) {
            valueIndex.remove(max);
        }

return max;
    }

privatevoidlinkBeforeTail(Node node){
        Node last = tail.prev;

        last.next = node;
        node.prev = last;

        node.next = tail;
        tail.prev = node;
    }

privatevoidunlink(Node node){
        Node left = node.prev;
        Node right = node.next;

        left.next = right;
        right.prev = left;

        node.prev = null;
        node.next = null;
    }
}

这里有个小点别改错了。

valueIndex 里面我用的是 Deque<Node>，不是 Set<Node>。

原因很简单：重复值要按入栈顺序处理。最大值如果出现多次，popMax() 要删离栈顶最近的那个，也就是最后入栈的那个最大值。

所以这里用：

bucket.removeLast();

不是随便删一个。

跑一下刚才那个例子：

MaxStack stack = new MaxStack();

stack.push(5);
stack.push(1);
stack.push(5);
stack.push(3);

System.out.println(stack.peekMax()); // 5
System.out.println(stack.popMax());  // 5
System.out.println(stack.top());     // 3
System.out.println(stack.pop());     // 3
System.out.println(stack.top());     // 1

这时候栈里剩下的是：

5, 1

说明删的是靠近栈顶的那个 5，没删错。

复杂度也比较干净。

push() 要写链表，再写 TreeMap，主要是 O(log n)。

pop() 要从 TreeMap 找对应桶，删除最后一个节点，整体也是 O(log n)，严格说删除桶本身才走树操作。

top() 是 O(1)。

peekMax() 是 O(log n) 或接近树取尾节点的成本。

popMax() 是 O(log n)。

有人会问，能不能用两个栈？

能，但只能解决 peekMax()，解决不了漂亮的 popMax()。

双栈写法大概是这样：

push(x) 时顺手记录当前最大值
pop() 时两个栈一起弹
peekMax() 直接看最大值栈顶

但是 popMax() 要删中间元素，两个栈就开始别扭了。你得把上面的元素倒出来，删完再倒回去。数据量小没事，数据量一大，日志里就会出现前面那种几十毫秒、几百毫秒的抖动。

最大栈这个题，看着像栈，其实考的是两个结构怎么互相留后门。

链表给 TreeMap 留了一个“按节点删除”的口子。

TreeMap 给链表留了一个“快速定位最大值”的口子。

只用一个结构硬扛，最后代码不是慢，就是乱。这个地方别省。