题目描述
验证栈序列
给定 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 <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。
数据结构
- 栈
算法思维
- 遍历、模拟法
解题要点
- 栈的后入先出特性
- 使用栈结构模拟题目中的情景
解题思路
一. Comprehend 理解题意
- 每个元素只有在下一个元素入栈前才能出栈
- 只有将要出栈的元素 == 当前栈顶元素时才能出栈
- 将要出栈的元素 != 当前栈顶的元素时，只有以下两种情况：
1.pushed 数组中还有未入栈的元素，此时需要继续入栈，继续判断，直到二者相等
2.pushed 数组中没有未入栈的元素了，将要出栈的元素找不到匹配，错误！！！
二. Choose 选择数据结构与算法
解法：栈模拟法
- 数据结构：栈
- 算法思维：遍历、模拟
代码流程
- 遍历 pushed 数组
- 判断栈顶元素是否 == popped 数组中将要出栈的元素
- 如果相等，直接出栈
- 如果不相等，且 pushed 数组中还有未入栈的元素，则继续压入下一个元素
- 如果不相等，但 pushed 数组中没有未入栈的元素了，则返回 false
- 若所有元素都顺利出栈，则返回 true
三. Code 编码实现基本解法
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
if (pushed.length == 0) return true;
Stack<Integer> stack = new Stack<>();
int i = 0, j = 0;
stack.push(pushed[i++]);
//1. 遍历 pushed 数组
while (!stack.isEmpty()){
//2. 判断栈顶元素是否 == popped 数组中将要出栈的元素
if (stack.peek() == popped[j]) {
//3.如果相等，直接出栈
stack.pop();
j++;
// 出栈后如果栈空了，要压入下一个元素
if (stack.isEmpty() && i<pushed.length){
stack.push(pushed[i++]);
}
} else if (i < pushed.length) {
//4. 如果不相等，且 pushed 数组中还有未入栈的元素，则压入下一个元素
stack.push(pushed[i++]);
} else {
//5.如果不相等，但 pushed 数组中没有未入栈的元素了，则返回 false
return false;
}
}
//6. 若所有元素都顺利出栈，则为 true
return true;
}
}
执行耗时：2 ms，击败了 90.16% 的Java用户
内存消耗：38.1 MB，击败了 77.85% 的Java用户
时间复杂度：O(n) -- 数组遍历
空间复杂度：O(n) -- 栈的内存空间
四. Consider 思考更优解
借鉴其他算法：
解法一是关注 “什么时候入栈”，而解法二则是关注 “什么时候出栈”
五. Code 编码实现最优解
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
int n = pushed.length;
Stack<Integer> stack = new Stack<>();
int j = 0;
//1.遍历入栈数组
for (int x : pushed) {
stack.push(x);
//2.每压入一个元素，循环判断：
// 当：栈不为空 && 还有未出栈的元素 && 栈顶元素 == 将要出栈元素 时，可以出栈
while (!stack.isEmpty() && j < n && stack.peek() == popped[j]) {
stack.pop();
j++;
}
}
//3.如果所有元素都成功出栈，则 j==n
return j == n;
}
}
执行耗时：2 ms，击败了 90.16% 的Java用户
内存消耗：38.2 MB，击败了 56.75% 的Java用户
时间复杂度：O(n) -- 数组的遍历
空间复杂度：O(n) -- 栈的内存空间
六. Change 变形与延伸
=== 待续 ===
