946. 验证栈序列

🟠   🔖  栈 数组 模拟  🔗 力扣 LeetCode

题目

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, orfalse otherwise.

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

Output: true

Explanation: We might do the following sequence:

push(1), push(2), push(3), push(4),

pop() -> 4,

push(5),

pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

Output: false

Explanation: 1 cannot be popped before 2.

Constraints:

• 1 <= pushed.length <= 1000
• 0 <= pushed[i] <= 1000
• All the elements of pushed are unique.
• popped.length == pushed.length
• popped is a permutation of pushed.

题目大意

给定 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 的一个排列

解题思路

这道题可以使用模拟栈的方法进行判断，使用一个辅助栈 stack，模拟 入栈（push）和出栈（pop）操作，最后通过判断栈是否为空来来验证序列的正确性。

1. 初始化：

   • 创建一个空栈 stack 来模拟栈的操作。
   • 设置一个变量 popIndex 为 0，表示当前需要匹配的出栈序列中的元素位置。

2. 遍历 pushed：

   • 将每个元素 item 入栈（stack.push(item)）。
   • 在每次入栈后，检查栈顶元素是否与 popped[popIndex] 相等：
     • 如果相等，说明当前出栈序列中的元素可以出栈，我们执行 stack.pop() 并将 popIndex 加 1。
     • 继续重复这个过程，直到栈顶元素与 popped[popIndex] 不相等或栈为空。

3. 验证结果：

   • 如果最终栈为空，说明 popped 是合法的出栈序列；否则不是。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 pushed 的长度，每个元素入栈一次，最多出栈一次，总操作次数是 O(n)，
• 空间复杂度：O(n)，栈最多存储 pushed 中的所有元素。

代码

/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
var validateStackSequences = function (pushed, popped) {
	let stack = []; // 模拟栈操作
	let popIndex = 0; // 指向出栈序列的当前位置

	for (let item of pushed) {
		stack.push(item); // 入栈操作
		// 栈顶元素与当前出栈元素相等时，执行出栈操作
		while (stack.length > 0 && stack[stack.length - 1] === popped[popIndex]) {
			stack.pop();
			popIndex++;
		}
	}

	// 如果栈为空，表示出栈序列是合法的
	return stack.length === 0;
};