当前位置：首页 > article >正文

leetcode946. 验证栈序列

article 2024/9/28 20:51:40

给定 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 之前弹出。
提示：

1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
pushed 的所有元素 互不相同
popped.length == pushed.length
popped 是 pushed 的一个排列

/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */ 
var validateStackSequences = function(pushed, popped) {
    const stack = [];
    const n = pushed.length;
    for (let i = 0, j = 0; i < n; i++) {
        stack.push(pushed[i]);
        while (stack.length && stack[stack.length - 1] == popped[j]) {
            stack.pop();
            j++;
        }
    }
    return stack.length === 0;
};

函数的主要逻辑如下：

创建一个空数组stack，用于模拟栈的操作。
获取pushed数组的长度n。
使用一个循环遍历pushed数组中的每个元素。
在每次迭代中，将当前元素推入栈中。
检查栈顶元素是否与popped数组中的当前元素相等。如果相等，则从栈中弹出该元素，并将popped数组的索引j加1。
继续执行步骤5，直到栈为空或栈顶元素与popped数组中的当前元素不相等。
当所有元素都被处理后，检查栈是否为空。如果栈为空，说明pushed和popped数组表示的是有效的栈操作序列，返回true；否则，返回false。

总结：主要是通过模拟栈的操作来验证给定的两个序列是否能够正确地模拟栈的推入和弹出操作。