946. 验证栈序列 - 力扣（LeetCode）42. 栈的压入、弹出序列 - AcWing题库

题目描述

关系

1535. 弹出序列 - AcWing题库

内容

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

假设压入栈的所有数字均不相等。

例如序列 $1,2,3,4,5$ 是某栈的压入顺序，序列 $4,5,3,2,1$ 是该压栈序列对应的一个弹出序列，但 $4,3,5,1,2$ 就不可能是该压栈序列的弹出序列。

注意：若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空，则视为是一个栈的压入、弹出序列。

数据范围

序列长度 $[0,1000]$。

样例

输入：[1,2,3,4,5]
      [4,5,3,2,1]

输出：true

问题分析

最初思路

思路分析

对于入栈序列中的每个元素，我们有两种操作：

1. 将这个数压入栈中；
2. 将这个数压入后弹出；

我们从输入序列的第一个数开始考虑。假设，有序列 ${\displaystyle [1,2,3,4,5]}$ ，对于 1，我们有两种选择，我们要么将其压入栈，要么压入后直接弹出。此时 1 是一定是压入栈不弹出的，因为输出序列第一个数不为 1.

对于 2，还是只能压入不弹出，因为第一个输出序列不为 2. 3 是同理的。

对于 4，由于输出序列第一数与其相同，所以，这个数一定是弹出的。此时栈中的元素为 ${\displaystyle [1,2,3]}$. 对于 5，同理。

剩下栈中的元素为 1,2,3，也是一个道理，只能弹出了。

所以可以总结出思路：判断当前栈顶元素师否和下一个要输出的数（在弹出序列中的）是一样的：

1. 一样，那么就必然要将栈顶元素弹出；
2. 不一样，当前元素必然不直接弹出，下一个元素进栈；

故而，每一个输出序列对于唯一一系列操作。这是一道模拟题。

执行流程设计

总结

代码实现

class Solution {
public:
    bool isPopOrder(vector<int> pushV,vector<int> popV) {
        if (pushV.size() != popV.size()) return false;
        
        stack<int> stk;
        int i = 0;
        for (auto v: pushV) {
            stk.push(v);
            
            while (stk.size() && stk.top() == popV[i]) {
                stk.pop();
                i++;
            }
        }
        
        return stk.empty();
    }
};