题目描述

给你一个目标数组 target 和一个整数 n。每次迭代，需要从 list = {1,2,3...,n} 中读取一个数字。使用栈操作 Push 和 Pop，构建目标数组 target。返回构建 target 所用的操作序列。

例如：target = [1,3]，n = 3，输出 ["Push","Push","Pop","Push"]。

解释：读取 1，Push（得到 [1]）；读取 2，Push（得到 [1,2]），但 2 不在 target 中，所以 Pop（得到 [1]）；读取 3，Push（得到 [1,3]），3 在 target 中。

解题思路

核心思想

题目本质是一个模拟问题。我们按顺序从 1 到 n 遍历数字，对于每个数字 i：

  1. 无论 i 是否在 target 中，我们都需要先执行 Push。
  2. 如果 i 不在 target 中，则紧接着执行 Pop（相当于 Push 之后马上 Pop 掉）。
  3. 如果 i 在 target 中，则保留，继续处理下一个数字。
  4. 当 target 中的所有数字都已处理完毕时，即可停止。

步骤分解

  1. 构建标记数组：创建一个长度为 n 的布尔标记数组 ans，将 target 中出现的元素对应位置标记为 1。
  2. 找到最大下标：遍历标记数组，找到 target 中最后一个元素在标记数组中的位置 index。我们只需要处理到该位置即可，因为之后的数字不需要 Push。
  3. 模拟操作：从 0 到 index 遍历标记数组：
    • 每个元素都 Push。
    • 如果该元素不在 target 中（标记为 0），则 Pop。

为什么只需要处理到 target 中最大元素的位置？

因为一旦处理完 target 中最大的数字，后续更大的数字不需要 Push（它们不会成为 target 的一部分），所以可以直接停止。

以 target = [1,3]，n = 3 为例：

  • target 中最大元素是 3，位置在 index=2
  • 遍历 i=0（数字 1标记=1）→ Push
  • i=1（数字 2标记=0）→ Push, Pop
  • i=2（数字 3标记=1）→ Push
  • 结果：["Push","Push","Pop","Push"]

复杂度分析

  • 时间复杂度：O(n)，遍历标记数组一次。
  • 空间复杂度：O(n)，需要标记数组和结果列表的空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package code.J1441;

import java.util.ArrayList;
import java.util.List;

public class J1441 {
    public List<String> buildArray(int[] target, int n) {
        List<String> res = new ArrayList<>();
        int[] ans = new int[n];
        for (int i : target) {
            ans[i - 1] = 1;
        }
        int index = 0;
        for (int i = 0; i < ans.length; i++) {
            if (ans[i] == 1) index = i;
        }
        for (int i = 0; i <= index; i++) {
            res.add("Push");
            if (ans[i] == 0) res.add("Pop");
        }
        return res;
    }
}