前言

🚀 个人主页：清风莫追
🔥 文章作为刷题笔记，如有问题欢迎指出，
🔥 希望能和大家一起加油，一起进步！

🌍 另外，给大家推荐一款神器：《牛客网》
🌍 无论是面试，还是刷题学习，都非常好用。而且调试在线编程题时，是可以对比测试数据对应的正确输出的。

文章目录

前言

1. 题目描述

2. 思路一：递归，借鉴树的三序遍历

2. 思路二：辅助栈

实现代码

结束语：

1. 题目描述

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

1,2,3,4,5

$1, 2, 3, 4, 5$ 是某栈的压入顺序，序列

4,5,3,2,1

$4, 5, 3, 2, 1$ 是该压栈序列对应的一个弹出序列，但

4,3,5,1,2

$4, 3, 5, 1, 2$ 就不可能是该压栈序列的弹出序列。

示例1

输入：
[1,2,3,4,5],[4,5,3,2,1]
返回值：
true
说明：
可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true

示例2

输入：
[1,2,3,4,5],[4,3,5,1,2]
返回值：
false
说明：
由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false

2. 思路一：递归，借鉴树的三序遍历

通过判断能否画出一颗树，来判断两个序列是否匹配

起初看到这个题目我还有点懵，但我很快就联想到了递归的方法，进而想起了关于树的三序遍历中有这样一个问题：已知树的中序和后序遍历序列，求前序遍历序列。
它们是怎么联系起来的呢？接下来我们以前面的第一个示例，来解释一下。

从最先弹出的
然后，我就不可抑制得想起了二叉树 （不要问我为什么，问就是掉了两根头发）
并且不难发现，将弹出序列倒过来，就刚好可以和压入序列对应，前者作为树的后序遍历序列，而后者作为中序遍历序列
后序遍历：
为什么要画出一颗树呢？还是回到我们的题：判断栈的压入、弹出序列是否可能匹配
我们可以设计这样一个判定：
如果通过栈的压入、弹出两个序列，可以成功画出一颗二叉树，那么这两个序列是可以匹配的

感觉突然就和树联系起来了，比较有趣，因此记录一下。
但仅仅是解决这个栈的问题，还有更棒的方法。

2. 思路二：辅助栈

作为一个关于栈的问题，真正用到栈才正常

设压入序列为push，弹出序列为pop，使用的辅助栈为stack

算法过程：

从push的第一个元素开始遍历，将一个元素压入stack中
尝试匹配stack的栈顶元素，与pop中还未成功匹配的首个元素
1）若元素相同，则在stack中弹出该元素，且该元素在pop中作为已成功匹配的元素。然后重复匹配操作。
2）若元素不同，则停止匹配
若push中元素全部入栈后，栈为空，则两个序列匹配

（也可以试试看这篇题解，里面有过程图）

实现代码

 /**
 * @param pushV int整型一维数组 
 * @param pushVLen int pushV数组长度
 * @param popV int整型一维数组 
 * @param popVLen int popV数组长度
 * @return bool布尔型
 */
bool IsPopOrder(int* pushV, int pushVLen, int* popV, int popVLen ) {
    int stack[1001] = {};    //辅助栈
    int top = -1;    //栈顶指针
    int i, j;    //i迭代push，j迭代pop
    for(i = 0, j = 0; i < pushVLen; i++){
        stack[++top] = pushV[i];
        while(top != -1 && stack[top] == popV[j]){
            j++;
            stack[top--] = 0;
        }
    }
    if(j == popVLen) {
        return true;
    }
    else {
        return false;
    }
}