053 · Build an Array With Stack Operations

algorithm
Published

July 6, 2026

My First Thoughts

嗯，这道题的 input 是一个 target 和一个数值 n。

操作包括 "Push" 和 "Pop"。

我们循环的应该是 n：

for i in range(1, n + 1):

每读到一个数字，首先都需要 "Push"：

result.append("Push")

然后如何判断呢？

如果 i in target，说明这个数字是最终数组里需要的数字，那就直接下一个。

否则，它只是路过的数字，不能留在数组里，所以要再加一个 "Pop"：

result.append("Pop")

这样整体应该可以。

然后是判断什么时候合适退出。因为 target 是递增序列，如果 i == target[-1]，这应该就是结束信号，否则就继续。

还有一个想法是：target 可以作为 set 来做。因为它是递增的，不会重复，所以可以用 set 节省 in 的判断时间。

甚至用过 i 后可以从 target 里删掉，节省后续判断：

target.remove(i)

然后删除后判断是否为空：

if not target:
    return result

大概会写成：

result = []
target = set(target)

for i in range(1, n + 1):
    result.append("Push")

    if i in target:
        target.remove(i)

        if not target:
            return result
    else:
        result.append("Pop")

return result

Why That Is Not Enough

上面的 set 写法可以通过，但它有一个小缺点：它没有直接表达 target 的顺序。

这题里，target 本来就是一个严格递增数组。我们从 1 到 n 读数字时，其实不需要问：

i 在不在整个 target 里面？

更自然的问题是：

i 是不是当前正在等待的那个 target 数字？

比如：

target = [1, 3]

一开始等待的是 1。读到 1，保留它，然后下一个等待目标变成 3。读到 2，它不是当前等待的 3，所以 "Push" 后要 "Pop"。读到 3，保留它，目标就完成了。

所以这里可以不用额外的 set，而是用一个指针 index 表示：

当前正在等待 target[index]。

这样状态会更贴近题意，也更容易解释为什么可以提前停止。

Final Idea

使用 index 指向当前还需要构造的目标数字。

一开始：

index = 0

表示现在正在等待 target[0]。

然后从 1 到 n 依次读取数字 i：

  • 每个 i 都必须先 "Push"
  • 如果 i == target[index]，说明这个数字应该保留，index 往后移动一位
  • 如果 i != target[index]，说明这个数字不是当前需要的数字，要马上 "Pop" 掉
  • 当 index == len(target) 时，说明整个 target 已经构造完成，可以直接返回 result

这个写法和 set 写法本质一样，都是模拟操作。区别是：set 在问“这个数字是不是目标之一”，指针在问“这个数字是不是当前要的目标”。后者更符合 target 严格递增这个条件。

Why It Works

题目规定，我们只能按顺序读取 1, 2, 3, ..., n。

所以当读到数字 i 时，有两种情况。

如果 i 正好等于 target[index]，说明它是下一个应该出现在结果数组里的数字。我们执行 "Push" 后保留它，并把 index 加一，表示接下来等待下一个目标数字。

如果 i 不等于 target[index]，因为数字只能越来越大，之后不会再回头读到 i。同时它又不是当前目标需要的数字，所以它不能留在数组里。题目要求每个读到的数字必须先 "Push"，因此这个时候只能再执行一次 "Pop" 把它删除。

当 index == len(target)，说明 target 中每一个数字都已经按顺序保留下来。题目说数组已经变成 target 时可以停止读取，所以不需要继续处理后面的数字。

比如：

target = [1, 3], n = 3

过程是：

i = 1，等待 target[0] = 1，Push 后保留，index 变成 1
i = 2，等待 target[1] = 3，Push 后 Pop
i = 3，等待 target[1] = 3，Push 后保留，index 变成 2

此时 index == len(target)，构造完成，返回：

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

Code

def buildArray(target, n):
    result = []
    index = 0

    for i in range(1, n + 1):
        result.append("Push")

        if i == target[index]:
            index += 1

            if index == len(target):
                return result
        else:
            result.append("Pop")

    return result

Complexity

Time \(O(n)\) - 最多从 1 遍历到 n，每个数字只处理一次
Space \(O(1)\) - 除了必须返回的 result，只用了一个指针 index

Takeaway

当目标数组有顺序，并且我们也是按顺序读输入时，通常可以用一个指针表示“当前正在等待哪个目标”。这比把整个目标放进 set 里判断 membership 更能保留题目的结构，也更容易写出提前停止条件。

← Quiz