Java 中验证栈序列

在 Java 中，验证给定的一系列压入和弹出组件是否可能通过堆栈的 后进先出 (LIFO) 行为生成的这个过程，被称为栈序列验证。为了模拟栈操作并确定弹出序列是否有效，提供了两个整数数组，一个用于压入序列，另一个用于弹出序列。通过解决这个问题，可以增强栈操作及其在实际应用中的限制。

为了实现这一点，通常会使用一个辅助栈，将元素从压入序列压入其中，并根据指定的弹出顺序弹出。如果每个元素都能按正确的顺序弹出而不会破坏栈的约束，则该序列被认为是有效的。

示例 1

输入

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

输出

true

解释

我们可以执行以下操作

push(2), push(1)

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

push(3), pop() -> 3

push(4), push(5)

pop() -> 5, pop() -> 4

该序列有效，因为每个元素都按正确的顺序弹出。

示例 2

输入

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

输出

true

解释

我们可以执行以下操作

push(1), push(2)

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

push(3), push(4), push(5)

pop() -> 5, pop() -> 4, pop() -> 3

该序列有效，因为每个元素都按正确的顺序弹出。

示例 3

输入

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

输出

false

解释

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

pop() -> 3

push(4), push(5)

pop() -> 5, pop() -> 4

尽管根据弹出序列，2 应该在 4 之前弹出，但此时它仍在栈中。

该序列无效，因为并非所有元素都按正确的顺序弹出。

方法：使用栈（模拟）

为了验证 压入和弹出操作 的顺序，代码使用了 Stack 数据结构。在遍历 push 数组的每个成员时，将其压入栈中。为了确保正确的顺序，当栈顶元素与 pop 数组中的下一个值匹配时，while 循环将弹出该值。循环条件有效地管理了验证，而 Stack 的使用提供了 LIFO（后进先出） 行为。通过 return 条件 stack.isEmpty() 可以确保所有元素都按正确的顺序弹出的序列的有效性。

实施

输出

 
true   

复杂度分析

上述代码的时间复杂度为 O(N)，空间复杂度为 O(N)，其中 N 表示元素的数量。

方法：使用两个指针（优化，无需栈）

作为 Java 内置 Stack 类的替代方案，该代码使用整数数组（stack[]）来实现基于数组的栈模拟。变量 top 作为栈的指针，push 和 pop 操作分别通过 stack[++top] = num 和 top-- 来模拟。根据 pop[] 序列，while 循环确保组件按正确的顺序被移除。序列的有效性由条件 top == -1 确定。

实施

输出

 
true   

复杂度分析

上述代码的时间复杂度为 O(N)，空间复杂度为 O(N)，其中 N 表示元素的数量。

方法：使用递归

代码使用递归来控制栈操作，而不是使用显式循环。递归辅助函数跟踪 push (i) 和 pop (j) 索引，并维护一个用于 LIFO 行为的栈。当所有组件都正确弹出时，基本情况将保证终止。push（stack.push(push[i])）和 pop（stack.pop()）操作根据序列的有效性通过条件递归来处理。

实施

输出

 
true   

复杂度分析

上述代码的时间复杂度为 O(N)，空间复杂度为 O(N)，其中 N 表示元素的数量。