Java实现 leetcode-946. 验证栈序列

这道题是试卷上经常出的考试题目，但是放在程序题中还是第一次做，使用了一个变量p模拟栈顶部。然后遍历出栈元素。（注释全在代码里了）

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int p = 0;//栈顶部界限
        int q = 0;//遍历pop数组
        while(q < popped.length){//遍历完了说明出栈顺序是对的
            if(p < 0) p = 0;//如果入栈界限小于零说明栈空了，回到起点，这一步是因为最后一步忽略已出栈元素可能会将顶部界限变为负数
            while(p < pushed.length && pushed[p] != popped[q]){//往上遍历入栈。
                p++;
            }
            if(p >= pushed.length) return false;//如果没有结果说明元素在栈里面，但是出栈只能是顶部元素或者还没入栈的元素。

            q++;//找到了pop数组遍历
            pushed[p] = -1;//赋值-1模拟出栈
            while(p >=0 && pushed[p] == -1) p--;//忽略已出栈的元素。
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

如果实在看不懂，拿出纸和笔画一下就知道了。