053 · Build an Array With Stack Operations

Problem

给定一个严格递增的整数数组 target，以及一个整数 n。

你有一个空数组。现在从 1 到 n 依次读取数字。每读到一个数字，你可以执行下面两种操作：

• "Push"：把当前数字加入数组
• "Pop"：删除数组最后一个数字

每个读到的数字必须先执行一次 "Push"。如果这个数字不应该留在最终数组里，可以再执行一次 "Pop" 把它删掉。

当数组已经变成 target 时，就可以停止读取后面的数字。

请返回：为了构造出 target，需要执行的操作列表。

题目保证：一定存在答案。

例如：

target = [1, 3]
n = 3

从 1 开始读：

读到 1：Push，数组变成 [1]
读到 2：Push 再 Pop，数组仍然是 [1]
读到 3：Push，数组变成 [1, 3]

所以答案是：

["Push", "Push", "Pop", "Push"]

Examples

示例 1

Input:  target = [1, 3], n = 3
Output: ["Push", "Push", "Pop", "Push"]

解释：读到 1 时保留它；读到 2 时先加入再删除；读到 3 时保留它。

示例 2

Input:  target = [1, 2, 3], n = 3
Output: ["Push", "Push", "Push"]

解释：每个读到的数字都正好需要保留，所以只需要执行 "Push"。

示例 3

Input:  target = [1, 2], n = 4
Output: ["Push", "Push"]

解释：数组已经变成 target 后就可以停止，不需要继续读取 3 和 4。

Constraints

• \(1 \leq\) target.length \(\leq 100\)
• \(1 \leq\) n \(\leq 100\)
• \(1 \leq\) target[i] \(\leq n\)
• target 严格递增

Link

• Original Problem

---

→ Solution