前言

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

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

---

文章目录

• 前言
• 1. 题目描述
• 2. 思路一：递归，借鉴树的三序遍历
• 2. 思路二：辅助栈
• • 实现代码

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）4
  3）在 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

感谢阅读