剑指offer - 栈的压入弹出序列 - JavaScript
剑指offer - 栈的压入弹出序列 - JavaScript
心谭博客
发布于 2020-04-21 15:26:42
发布于 2020-04-21 15:26:42
题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
解法 1:辅助栈
需要一个辅助栈，来模拟出入栈的过程。算法流程如下：
- 依次遍历压入序列的元素，检查当前元素和弹出序列的第一个元素是否相等：
- 若不相等，将元素压入辅助栈
- 若相等：
- 元素不入辅助栈，且取出弹出序列的第一个元素。
- 依次比较弹出序列元素是否和栈元素，批量删除
- 最后，检查辅助栈和弹出队列是否均为空。
时间复杂度是 O(N^2)，空间复杂度是 O(N)。代码实现如下：
// ac地址：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
// 原文地址：https://xxoo521.com/2020-01-31-stack-pop-push/
/**
* @param {number[]} pushed
* @param {number[]} popped
* @return {boolean}
*/
var validateStackSequences = function(pushed, popped) {
const stack = []; // 辅助栈
pushed.forEach(v => {
if (v === popped[0]) {
popped.shift();
let i = 0;
const poppedLength = popped.length;
for (; i < poppedLength; ++i) {
if (stack[stack.length - 1] === popped[i]) {
stack.pop();
} else {
break;
}
}
popped.splice(0, i);
} else {
stack.push(v);
}
});
return !stack.length && !popped.length;
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-01-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录