LeetCode 题解工作台
用栈操作构建数组
给你一个数组 target 和一个整数 n 。 给你一个空栈和两种操作： "Push" ：将一个整数加到栈顶。 "Pop" ：从栈顶删除一个整数。 同时给定一个范围 [1, n] 中的整数流。 使用两个栈操作使栈中的数字（从底部到顶部）等于 target 。你应该遵循以下规则： 如果整数流不为空，从…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
我们定义一个变量 表示当前待读取的数字，初始时 $\textit{cur} = 1$，用一个数组 存储答案。 接下来，我们遍历数组 中的每个数字 ：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个数组 target 和一个整数 n。
给你一个空栈和两种操作：
"Push"：将一个整数加到栈顶。"Pop"：从栈顶删除一个整数。
同时给定一个范围 [1, n] 中的整数流。
使用两个栈操作使栈中的数字（从底部到顶部）等于 target。你应该遵循以下规则：
- 如果整数流不为空，从流中选取下一个整数并将其推送到栈顶。
- 如果栈不为空，弹出栈顶的整数。
- 如果，在任何时刻，栈中的元素（从底部到顶部）等于
target，则不要从流中读取新的整数，也不要对栈进行更多操作。
请返回遵循上述规则构建 target 所用的操作序列。如果存在多个合法答案，返回 任一 即可。
示例 1：
输入：target = [1,3], n = 3 输出：["Push","Push","Pop","Push"] 解释：一开始栈为空。最后一个元素是栈顶。 从流中读取 1 并推入数组。s = [1]。 从流中读取 2 并推入数组。s = [1,2]。 从栈顶删除整数。s = [1]。 从流中读取 3 并推入数组。s = [1,3]。
示例 2：
输入：target = [1,2,3], n = 3 输出：["Push","Push","Push"] 解释：一开始栈为空。最后一个元素是栈顶。 从流中读取 1 并推入数组。s = [1]。 从流中读取 2 并推入数组。s = [1,2]。 从流中读取 3 并推入数组。s = [1,2,3]。
示例 3：
输入：target = [1,2], n = 4 输出：["Push","Push"] 解释：一开始栈为空。最后一个元素是栈顶。 从流中读取 1 并推入数组。s = [1]。 从流中读取 2 并推入数组。s = [1,2]。 由于栈（从底部到顶部）等于 target，我们停止栈操作。 从流中读取整数 3 的答案不被接受。
提示：
1 <= target.length <= 1001 <= n <= 1001 <= target[i] <= ntarget严格递增
解题思路
方法一：模拟
我们定义一个变量 表示当前待读取的数字，初始时 ，用一个数组 存储答案。
接下来，我们遍历数组 中的每个数字 ：
- 如果 ，我们将 和 依次加入答案，直到 ；
- 然后我们将 加入答案，表示读取数字 ；
- 接着，我们将 加一，继续处理下一个数字。
遍历结束后，返回答案数组即可。
时间复杂度 ，其中 是数组 的长度。忽略答案数组的空间消耗，空间复杂度 。
class Solution:
def buildArray(self, target: List[int], n: int) -> List[str]:
ans = []
cur = 1
for x in target:
while cur < x:
ans.extend(["Push", "Pop"])
cur += 1
ans.append("Push")
cur += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Can the candidate optimize the handling of stack operations for larger inputs?
- question_mark
Is the candidate able to clearly explain the pattern of stack operations for non-target numbers?
- question_mark
Does the candidate understand why a 'Push' followed by 'Pop' works to discard unnecessary numbers?
常见陷阱
外企场景- error
Pushing unnecessary numbers to the stack without checking if they match the target array.
- error
Not recognizing that 'Pop' must be used for numbers that aren't part of the target array.
- error
Failing to handle the edge cases where the stack operation sequence must be minimized.
进阶变体
外企场景- arrow_right_alt
Change the target array to include non-consecutive integers.
- arrow_right_alt
Modify the range of n to exceed the length of the target array.
- arrow_right_alt
Alter the operations so that only 'Push' can be used, forcing different solutions.