946. 验证栈序列
题目描述
输入两个整数数组 pushed 和 popped。pushed 中的值互不相同，popped 是 pushed 的一个排列。
从一个空栈开始，按 pushed 的顺序依次入栈，期间可以在任意时刻出栈。问能否让出栈的顺序正好是 popped。
能做到返回 true，否则返回 false。
示例 1
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 输出：true
解释：依次压入 1 到 4，弹出 4；压入 5，再依次弹出 5、3、2、1。
示例 2
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2] 输出：false
解释：弹出 4、3、5 之后，栈顶是 2，无法先弹出 1。
数据范围
1 <= pushed.length <= 10000 <= pushed[i] <= 1000pushed中的元素两两不同。popped.length == pushed.lengthpopped是pushed的一个排列。
解题思路
直接用一个真实的栈模拟。按 pushed 的顺序入栈，每入一个元素，就检查栈顶是否等于 popped 中下一个要弹出的元素，相等就立刻弹出。元素互不相同，所以“能弹就弹”是唯一正确的选择：如果现在不弹，它会被后面入栈的元素压住，再也弹不出来。最后看 popped 是否全部被匹配。
为什么正确
popped[:j] 已经按顺序弹出；栈中元素从底到顶是已入栈但还未弹出的元素，且栈顶不等于 popped[j]（除非刚入栈还未检查）。
复杂度分析
时间 O(n)，每个元素最多入栈、出栈各一次；空间 O(n)。
易错点
while 里要先判断栈非空再访问栈顶；并且弹出要用 while 而不是 if，一次入栈后可能连续弹出多个元素。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stack = []
j = 0
for x in pushed:
stack.append(x)
while stack and stack[-1] == popped[j]:
stack.pop()
j += 1
return j == len(popped)class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Deque<Integer> stack = new ArrayDeque<>();
int j = 0;
for (int x : pushed) {
stack.push(x);
while (!stack.isEmpty() && stack.peek() == popped[j]) {
stack.pop();
j++;
}
}
return j == popped.length;
}
}class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
vector<int> stack;
int j = 0;
for (int x : pushed) {
stack.push_back(x);
while (!stack.empty() && stack.back() == popped[j]) {
stack.pop_back();
j++;
}
}
return j == (int)popped.size();
}
};func validateStackSequences(pushed []int, popped []int) bool {
stack := []int{}
j := 0
for _, x := range pushed {
stack = append(stack, x)
for len(stack) > 0 && stack[len(stack)-1] == popped[j] {
stack = stack[:len(stack)-1]
j++
}
}
return j == len(popped)
}var validateStackSequences = function(pushed, popped) {
const stack = [];
let j = 0;
for (const x of pushed) {
stack.push(x);
while (stack.length && stack[stack.length - 1] === popped[j]) {
stack.pop();
j++;
}
}
return j === popped.length;
};function validateStackSequences(pushed: number[], popped: number[]): boolean {
const stack: number[] = [];
let j = 0;
for (const x of pushed) {
stack.push(x);
while (stack.length && stack[stack.length - 1] === popped[j]) {
stack.pop();
j++;
}
}
return j === popped.length;
}