Java Stack peek()原理及双栈求最大值实现疑问

参考实现代码 #

import java.util.Scanner;
import java.util.Stack;

// 入栈、出栈、查询最大值三类操作均为O(1)时间复杂度
public class Solution {
    public static void main(String[] args) {
        Stack<Integer> stack    = new Stack<Integer>();
        Stack<Integer> maxStack = new Stack<Integer>(); // 维护最大值序列

        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        for (int i = 0; i < N; i++) {
            int query = scan.nextInt();
            switch (query) {
                case 1:
                    int x = scan.nextInt();
                    stack.push(x);
                    if (maxStack.isEmpty() || x >= maxStack.peek()) {
                        maxStack.push(x);
                    }
                    break;
                case 2:
                    int poppedValue = stack.pop();
                    if (poppedValue == maxStack.peek()) {
                        maxStack.pop();
                    }
                    break;
                case 3:
                    System.out.println(maxStack.peek());
                    break;
                default:
                    break;
            }
        }        
        scan.close();
    }
}

核心逻辑说明 #

maxStack从来不是存储主栈的全量元素，只严格按顺序存储主栈每一个状态下的全局最大值，从规则上就保证栈顶永远是当前全局最大值，根本不会出现「中间有更大值没被记录」的情况，维护规则分两个环节卡死：

• 入栈规则：每次往主栈压入新元素x时，只有两种情况会把x同步压入maxStack：
  1. maxStack为空（也就是主栈刚插入第一个元素，此时这个元素必然是全局最大值）
  2. x大于等于maxStack当前栈顶值
     这一步的本质是：maxStack的栈顶永远是插入x之前整个主栈的最大值，如果新插入的x比这个值还大，那x就会成为新的全局最大值，必须放到maxStack栈顶；如果x比当前栈顶最大值小，那它永远不可能成为全局最大值——除非所有比它大的元素都被弹出主栈，而这些更大的元素早就按出现顺序存在maxStack里了。
• 出栈规则：每次从主栈弹出元素时，会先判断弹出值是否等于maxStack的栈顶：
  1. 如果相等，说明当前弹出的就是之前的全局最大值，这个值移除后，新的全局最大值就是maxStack弹出旧栈顶后的新栈顶
  2. 如果不相等，说明被弹出的元素从来没成为过全局最大值，它的移除完全不影响当前全局最大值，maxStack不需要做任何变动

举个实际走查例子就能看懂，比如按顺序执行入栈3、入栈1、入栈4、入栈2：

1. 入3：maxStack为空，压入3，maxStack为[3]，栈顶3是全局最大值
2. 入1：1小于当前maxStack栈顶3，不压入maxStack，maxStack保持[3]，栈顶3仍是全局最大值
3. 入4：4大于等于3，压入maxStack，maxStack为[3,4]，栈顶4是全局最大值
4. 入2：2小于4，不压入maxStack，maxStack保持[3,4]，栈顶4是全局最大值
   此时主栈元素从底到顶是3、1、4、2，确实存在中间元素3比栈顶2大，但maxStack的栈顶是4，是比3更大的全局最大值，根本不存在漏记的问题。
   后续执行出栈时逻辑也完全自洽：
5. 弹2：2不等于maxStack栈顶4，不改动maxStack，栈顶仍为4，对应剩余主栈[3,1,4]的最大值正确
6. 弹4：4等于maxStack栈顶4，弹出maxStack栈顶，maxStack变为[3]，栈顶3对应剩余主栈[3,1]的最大值正确
7. 弹1：1不等于3，不改动maxStack，栈顶仍为3，对应剩余主栈[3]的最大值正确
8. 弹3：3等于maxStack栈顶3，弹出maxStack栈顶，双栈均为空，状态正确

额外提一句代码里判断条件用>=而不是>的原因：是为了处理重复最大值的边界情况，比如连续压入两个5，如果不用>=，第二个5不会进入maxStack，弹出第一个5时就会错误把maxStack里的5弹走，导致剩下的5没有对应的最大值记录。

内容的提问来源于stack exchange，提问作者Ahir