验证栈序列（ LeetCode 946 ）
一、题目描述
给定 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 <= 10000 <= pushed[i] <= 1000pushed的所有元素 互不相同popped.length == pushed.lengthpopped是pushed的一个排列
二、题目解析
这道题目的一个难点在于理解题意，我来给大家翻译一下。
给定了两个数组 pushed 和 popped ，从头到尾的遍历 pushed ，在遍历的过程中将 pushed 中的元素添加到一个栈中，加入之后，有两个操作：
- 1、继续添加
pushed后面的元素到栈中，比如加入 1 之后，继续加入 2 。 - 2、把栈中的栈顶元素取出来（可重复操作）
按照这样的规则进行操作，判断一下，pushed 数组能否借助这个栈输出为 poped 数组这样的排序。
比如：pushed 数组为 1 2 3 4 5，那么它可以输出为 4 5 3 2 1 这样的排序数组。
但是，pushed 数组为 1 2 3 4 5，它不能输出为 4 5 3 1 2 这样的排序数组。
理解清楚题意之后，操作点实际上就是在这个栈上面了，只需要每次都借助先入后出的特点即可。
具体操作如下：
- 1、设置一个索引 index 表示 popped 数组中元素的下标，判断该索引指向的元素能否正常的出栈
- 2、遍历 pushed 数组中的每个元素，在遍历 pushed 数组时，把当前遍历的元素加入到栈中
- 3、加入完之后，不断的执行以下的判断
-
- 3.1、栈中是否有元素
- 3.2、栈顶元素是否和 popped 当前下标的元素相同
- 4、如果同时满足这两个条件，说明这个元素可以满足要求，即可以在最初空栈上进行推入 push 和弹出 pop 操作
- 5、遍历完 pushed 数组中的每个元素之后，如果发现栈不为空，那么说明出栈序列不合法，返回 false
- 6、遍历完 pushed 数组中的每个元素之后，如果发现栈为空，那么说明出栈序列合法，返回 true
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 验证栈序列（ LeetCode 946 ）:https://leetcode-cn.com/problems/validate-stack-sequences/
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
// 利用栈来模拟入栈和出栈操作
Stack<Integer> s = new Stack<Integer>();
// index 表示 popped 数组中元素的下标
// 比如 popped 是 [4,5,3,2,1]
// 那么第 0 个下标元素是 4 这个数字
// 先去判断这个数字能否正常的出栈
int index = 0;
// 遍历 pushed 数组中的每个元素
for(int i = 0 ; i < pushed.length; i ++){
// 在遍历 pushed 数组时，把当前遍历的元素加入到栈中
s.push(pushed[i]);
// 加入完之后，不断的执行以下的判断
// 1、栈中是否有元素
// 2、栈顶元素是否和 popped 当前下标的元素相同
// 如果同时满足这两个条件
// 说明这个元素可以满足要求，即可以在最初空栈上进行推入 push 和弹出 pop 操作
while(!s.isEmpty() && popped[index] == s.peek()){
// 那么就把栈顶元素弹出
s.pop();
// 同时 index++，观察 popped 下一个元素
index++;
}
}
// 遍历完 pushed 数组中的每个元素之后，如果发现栈不为空
if(!s.isEmpty()){
// 那么说明出栈序列不合法，返回 false
return false;
}
// 否则返回 true
return true;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 验证栈序列（ LeetCode 946 ）:https://leetcode-cn.com/problems/validate-stack-sequences/
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
// 利用栈来模拟入栈和出栈操作
stack<int> s ;
// index 表示 popped 数组中元素的下标
// 比如 popped 是 [4,5,3,2,1]
// 那么第 0 个下标元素是 4 这个数字
// 先去判断这个数字能否正常的出栈
int index = 0;
// 遍历 pushed 数组中的每个元素
for(int i = 0 ; i < pushed.size(); i ++){
// 在遍历 pushed 数组时，把当前遍历的元素加入到栈中
s.push(pushed[i]);
// 加入完之后，不断的执行以下的判断
// 1、栈中是否有元素
// 2、栈顶元素是否和 popped 当前下标的元素相同
// 如果同时满足这两个条件
// 说明这个元素可以满足要求，即可以在最初空栈上进行推入 push 和弹出 pop 操作
while(!s.empty() && popped[index] == s.top()){
// 那么就把栈顶元素弹出
s.pop();
// 同时 index++，观察 popped 下一个元素
index++;
}
}
// 遍历完 pushed 数组中的每个元素之后，如果发现栈不为空
if(!s.empty()){
// 那么说明出栈序列不合法，返回 false
return false;
}
// 否则返回 true
return true;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 验证栈序列（ LeetCode 946 ）:https://leetcode-cn.com/problems/validate-stack-sequences/
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
# 利用栈来模拟入栈和出栈操作
stack = []
# index 表示 popped 数组中元素的下标
# 比如 popped 是 [4,5,3,2,1]
# 那么第 0 个下标元素是 4 这个数字
# 先去判断这个数字能否正常的出栈
index = 0
# 遍历 pushed 数组中的每个元素
for item in pushed:
# 在遍历 pushed 数组时，把当前遍历的元素加入到栈中
stack.append(item)
# 加入完之后，不断的执行以下的判断
# 1、栈中是否有元素
# 2、栈顶元素是否和 popped 当前下标的元素相同
# 如果同时满足这两个条件
# 说明这个元素可以满足要求，即可以在最初空栈上进行推入 push 和弹出 pop 操作
while stack and stack[-1] == popped[index] :
# 那么就把栈顶元素弹出
stack.pop()
# 同时 index++，观察 popped 下一个元素
index += 1
# 遍历完 pushed 数组中的每个元素之后，如果发现栈不为空
if stack :
# 那么说明出栈序列不合法，返回 False
return False
# 否则返回 True
return True
