输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof
解题思路
扫描数组pushed, 并用一个索引指向popped, 将pushed当前遍历的元素压入栈
当刚入栈的pushed元素不是popped索引所指元素时, 继续往后扫描pushed
反之弹出栈顶元素, 并将popped的索引右移
如果遍历完整个数组, 栈中还有剩余元素, 则返回false, 栈为空则返回true
代码
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
if (pushed == null || popped == null) {
return false;
}
Deque<Integer> stack = new ArrayDeque<>();
int popIndex = 0;
// 当pushed栈顶不是popped的栈顶时, 将pushed压入辅助栈
for (int num : pushed) {
stack.push(num);
while (!stack.isEmpty() && stack.element() == popped[popIndex]) {
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
}
