31. 栈的压入、弹出序列

题目链接

Leetcode

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。

解题思路

使用一个栈来模拟压入弹出操作：按压入序列 putIn 依次入栈，每次入栈后，只要栈顶等于弹出序列 takeOut 中下一个要弹出的元素，就执行出栈操作并将 popIndex 往后移一位，继续进行判断。全部压入后栈为空，说明 takeOut 是合法的弹出顺序。

例如检查 4,5,3,2,1：压入 1～4 后栈顶 4 等于第一个要弹出的元素，弹出 4；压入 5 后弹出 5，此时栈顶依次是 3、2、1，与剩下的弹出序列一致，全部弹出，栈为空。检查 4,3,5,1,2 时，弹出 4、3、5 之后栈中从底到顶是 1、2，栈顶 2 不等于下一个要弹出的 1，而元素已经全部压入，栈不为空，返回 false。

public boolean validateBookSequences(int[] putIn, int[] takeOut) {
    int n = putIn.length;
    Stack<Integer> stack = new Stack<>();
    for (int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) {
        stack.push(putIn[pushIndex]);
        while (popIndex < n && !stack.isEmpty() && stack.peek() == takeOut[popIndex]) {
            stack.pop();
            popIndex++;
        }
    }
    return stack.isEmpty();
}