LeetCode946：验证栈序列

给定 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 之前弹出。 提示： 0 <= pushed.length == popped.length <= 10000 <= pushed[i], popped[i] < 1000pushed 是 popped 的排列。

解析：

     判断一个序列是否是出栈序列。改题目也是用栈完成，用栈存储pushed中的数据，当遇到popped中最前边未匹配的数据时，出栈，否则继续压栈。如果pushed全部压栈，栈顶元素和popped最前未匹配数据不相等，则返回false。最后如果栈非空，则返回false。

代码：

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { if (pushed.size() != popped.size()) return false; stack<int>pushStack; int j = 0;//pushed的下标 for (int i = 0; i < popped.size(); ) { while (pushStack.empty() || (popped[i] != pushStack.top() && j < pushed.size())) { pushStack.push(pushed[j++]); } while (!pushStack.empty() && popped[i] == pushStack.top()) { pushStack.pop(); i++; } if (!pushStack.empty() && j>=pushed.size() && popped[i] != pushStack.top()) return false; } return pushStack.empty(); }

虽然最后做对了，但是改了好几次。还是对题目不够熟悉。有了清晰的思路再写代码。