题目描述
验证栈序列
给定 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 变形与延伸
=== 待续 ===
网友评论