1441. 用栈操作构建数组

🎯 问题描述

描述：
给你一个数组 target 和一个整数 n。每次迭代，需要从列表 list = {1, 2, 3, ..., n} 中依序读取一个数字。
请使用下述操作来构建目标数组 target：

“Push”：从 list 中读取一个新元素，并将其推入数组中。
“Pop”：删除数组中的最后一个元素。

如果目标数组构建完成，就停止读取更多元素。题目数据保证目标数组严格递增。请返回构建目标数组所用的操作序列。

说明：

这是一个模拟类问题。
核心策略：
- 我们需要按顺序遍历 1 到 n 的数字。
- 对于每个数字 i，它要么是我们需要的（存在于 target 中），要么是不需要的。
- 如果是需要的，执行 “Push”。
- 如果是不需要的，执行 “Push” 紧接着执行 “Pop”（相当于读取后丢弃）。
- 一旦 target 构建完成，立即停止。
示例：
示例 1：

输入：target = [1,3], n = 3
输出：["Push","Push","Pop","Push"]
解释：
- 读取 1：是目标，Push -> [1]
- 读取 2：不是目标，Push -> [1,2]，Pop -> [1]
- 读取 3：是目标，Push -> [1,3]
- 完成。

💻 解题思路

思路1：模拟 + 双指针

核心逻辑

初始化：
- ans：用于存储操作序列。
- x：指向 target 数组的当前下标，表示我们正在等待匹配 target[x]。
遍历数据流：
- 使用循环变量 i 从 1 遍历到 n。
- 终止条件：如果 x 已经等于 target 的长度，说明目标数组已构建完成，直接 break。
判断与操作：
- 情况 A：匹配 (i == target[x])
  - 当前数字 i 正是我们需要的。
  - 执行 “Push”。
  - 指针 x 向后移动 (x++)，准备匹配下一个目标数字。
- 情况 B：不匹配 (i != target[x])
  - 当前数字 i 不是我们需要的（因为 target 是递增的，且 i 小于当前目标值，或者 i 根本不在 target 中）。
  - 执行 “Push”（读入），紧接着执行 “Pop”（丢弃）。
  - 指针 x 不动，继续等待下一个目标。

代码实现

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        ans = []
        m = len(target)
        x = 0  # x 指向 target 中当前需要匹配的元素下标
        
        # 遍历从 1 到 n 的数据流
        for i in range(1, n + 1):
            # 如果 target 已经全部匹配完成，提前结束
            if x == m:
                break
            # 如果当前数字 i 等于目标数字 target[x]
            elif i == target[x]:
                ans.append("Push")
                x += 1  # 移动到下一个目标
            # 如果当前数字 i 不等于目标数字
            else:
                ans.append("Push")
                ans.append("Pop")
                
        return ans

📊 性能分析

时间复杂度： $O(N)$ $O (N)$
- 最坏情况下，我们需要遍历完 1 到 n 的所有数字（例如 target 的最后一个元素是 n）。
- 但在很多情况下会提前结束，实际运行时间通常小于 $O(N)$ 。
空间复杂度： $O(1)$ $O (1)$
- 除了存储结果的 ans 列表外，只使用了常数级别的额外变量 (m, x, i)。
- 注意：结果列表本身的空间不计入额外空间复杂度。

思考

为什么不需要显式的栈？
- 虽然题目描述涉及栈操作，但我们实际上只需要记录操作序列（“Push”/“Pop”），并不需要真正维护一个栈来存储数字。因为我们是从 1 到 n 顺序读取的，逻辑上很清楚哪些数字被保留了。
target 的严格递增性质：
- 题目保证 target 是严格递增的，这非常关键。这意味着我们只需要按顺序匹配即可。如果 i 小于 target[x]，说明 i 不在目标中；如果 i 等于 target[x]，说明匹配成功。不会出现 i 大于 target[x] 的情况（除非已经匹配完了）。
提前终止的重要性：
- 代码中的 if x == m: break 是必须的。
- 例如 target = [1, 2], n = 4。当我们匹配完 2 之后，就不需要再处理 3 和 4 了，直接停止可以节省时间。