前言

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

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

@[toc]

1. 题目描述

描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列$1,2,3,4,5$是某栈的压入顺序，序列$4,5,3,2,1$是该压栈序列对应的一个弹出序列，但$4,3,5,1,2$就不可能是该压栈序列的弹出序列。

1. $0<=pushV.length==popV.length<=1000$
   

2. $-1000<=pushV[i]<=1000$
   

3. $pushV的所有数字均不相同$
   

示例 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. 思路一：递归，借鉴树的三序遍历

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

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

• 从最先弹出的$4$开始看，我们可以把压入序列切割成$3$个部分：1）在 4 之前压入的序列 2）43）在 4 之后压入的序列那么就可以形成一个递归结构，因为 4 前后的两个序列仍然可以这样划分为 3 个部分，直至只有一个元素而不可划分为止。

• 然后，我就不可抑制得想起了二叉树 （不要问我为什么，问就是掉了两根头发）

• 并且不难发现，将弹出序列倒过来，就刚好可以和压入序列对应，前者作为树的后序遍历序列，而后者作为中序遍历序列后序遍历：$A>B>4$中序遍历：$A>4>B$==我们可以画出一棵这样的二叉树来表示前面的递归结构==：

• 为什么要画出一颗树呢？还是回到我们的题：判断栈的压入、弹出序列是否可能匹配我们可以设计这样一个判定：==如果通过栈的压入、弹出两个序列，可以成功画出一颗二叉树，那么这两个序列是可以匹配的==

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

2. 思路二：辅助栈

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

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

算法过程：

1. 从push的第一个元素开始遍历，将一个元素压入stack中

2. 尝试匹配stack的栈顶元素，与pop中还未成功匹配的首个元素 1）若元素相同，则在stack中弹出该元素，且该元素在pop中作为已成功匹配的元素。然后重复匹配操作。 2）若元素不同，则停止匹配

3. 若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;    }}

结束语：

今天的分享就到这里啦，快来加入刷题大军叭！👉点击开始刷题学习👈

感谢阅读