经典问题——验证栈序列

我们先来看题目描述：

给定 pushed 和 popped 两个序列，每个序列中的值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true ；否则，返回 false 。

示例 1：

输入：pushed = [1,2,3,4,5] , popped = [4,5,3,2,1]

输出：true

解释：我们可以按以下顺序执行：push(1) , push(2) , push(3) , push(4) , pop() -> 4 , push(5) , pop() -> 5 , pop() -> 3, pop() -> 2 , pop() -> 1 。

示例 2：

输入：

pushed = [1,2,3,4,5] , popped = [4,3,5,1,2]

输出：

false

解释：

1 不能在 2 之前弹出。

提示：

1 <= pushed.length <= 1000 0 <= pushed[i] <= 1000 pushed 的所有元素互不相同 popped.length == pushed.length popped 是 pushed 的一个排列。

解析：

只要模拟入栈和出栈的过程，将一个数进行入栈操作的时候检查该数是否为下一个要出栈的数，如果是就弹出该数，并继续检查栈中的数。如果能扫描完所有要出栈的数，就是一个合法的栈序列。

Java 代码实现：（使用 ArrayList 模拟栈）

class Solution { public boolean validateStackSequences(int[] pushed, int[] popped) { List<Integer> S=new ArrayList<>(); int j=0; for(int i=0;i<pushed.length;i++){ S.add(pushed[i]); while(S.size()>0&&j<popped.length&&S.get(S.size()-1)==popped[j]){ S.remove(S.size()-1); j++; } } return j==popped.length; } }

C++ 代码实现：（直接用 STL stack ）

class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { stack<int>S; int n=pushed.size(); int j=0; for(int i=0;i<n;i++){ S.push(pushed[i]); while(S.size()>0&&j<n&&S.top()==popped[j]){ S.pop(); j++; } } return j==n; } };