31.栈的压入、弹出序列

raylan.chen大约 2 分钟

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        if (putIn == null || takeOut == null) return false;

        //i 指向 putIn，j 指向 takeOut
        int i = 0;
        int j = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        //putIn[i] 进栈
        if (putIn.length != 0) stack.offerLast(putIn[i++]);
        while (j < takeOut.length) {
            //判断栈顶是否等于takeOut，相等则出栈，不等则出栈元素可能位于putIn中，继续进栈
            if (!stack.isEmpty() && stack.getLast() == takeOut[j]) {
                stack.removeLast();
                j++;
            } else {
                if (i >= putIn.length) break;
                stack.offerLast(putIn[i++]);
            }
        }
        if (i == putIn.length && j == takeOut.length) return true;
        else return false;
    }
}

先让 putIn 第一个元素进栈并让 i 指向 putIn 的下一个进栈元素，随后对比是否等于 takeOut

相等，则出栈（出栈可能连续出栈，出完一个又出一个），j++，j 为指向 takeOut 的下一个对比元素

不等，则可能在 putIn 的后续元素中，继续进栈再对比，i++

判断结果是否为 true，i 和 j 都遍历完成则为 true，有一个没完成则为 false

判断特殊情况

while 循环中 i 不可能一直增长，得找个破除循环办法

测试用例中，putIn.length == 0 又或者 takeOut.length == 0 时该怎么办

putIn == null 又或者 takeOut == null 又该怎么办

优秀题解

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num : putIn) {
            stack.push(num); // num 入栈
            while(!stack.isEmpty() && stack.peek() == takeOut[i]) { // 循环判断与出栈
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/solutions/215152/mian-shi-ti-31-zhan-de-ya-ru-dan-chu-xu-lie-mo-n-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码感觉精简了好多，一个 for 遍历 putIn，直接在循环里进第一个元素，进栈然后对比，里面套一个 while 实现一直出栈

返回直接判断栈是否刚好元素全部出去了

31.栈的压入、弹出序列

31.栈的压入、弹出序列

参考链接

个人尝试

优秀题解