用栈操作构建数组

难度: Medium

给你一个数组 target 和一个整数 n。每次迭代，需要从 list = { 1 , 2 , 3 ..., n } 中依次读取一个数字。

请使用下述操作来构建目标数组 target ：

"Push"：从 list 中读取一个新元素，并将其推入数组中。
"Pop"：删除数组中的最后一个元素。
如果目标数组构建完成，就停止读取更多元素。

题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。

请返回构建目标数组所用的操作序列。如果存在多个可行方案，返回任一即可。

示例 1：

输入：target = [1,3], n = 3
输出：["Push","Push","Pop","Push"]
解释： 
读取 1 并自动推入数组 -> [1]
读取 2 并自动推入数组，然后删除它 -> [1]
读取 3 并自动推入数组 -> [1,3]

示例 2：

输入：target = [1,2,3], n = 3
输出：["Push","Push","Push"]

示例 3：

输入：target = [1,2], n = 4
输出：["Push","Push"]
解释：只需要读取前 2 个数字就可以停止。

提示：

1 <= target.length <= 100
1 <= n <= 100
1 <= target[i] <= n
target 严格递增

Submission

运行时间: 23 ms

内存: 16.0 MB

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        if not target:
            return []

        i = 0
        
        res = []
        for num in range(1, n + 1):
            res.append("Push")
            if num == target[i]:
                i += 1
            else:
                res.append("Pop")
            
            if i >= len(target):
                break
        
        return res

Explain

这个题解通过模拟从1到n的数字读取和根据条件进行Push或Pop操作以构建目标数组target。给定的target是严格递增的，算法从1开始递增地读取数字，对于每个数字，首先执行Push操作将其加入栈（虽然这里没有显式的栈，但可以认为是虚拟的）。接着，检查这个数字是否是目标数组target中当前需要的数字，如果是，则移动目标数组的索引i；如果不是，执行Pop操作以撤销前一步的Push。这个过程持续到处理完所有target中的数字为止。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        if not target:
            return []

        i = 0
        
        res = []
        for num in range(1, n + 1):
            res.append("Push")  # 尝试将当前数字推入虚拟栈
            if num == target[i]:
                i += 1  # 当前数字是目标数组的一部分，移动目标索引
            else:
                res.append("Pop")  # 当前数字不是目标数组的一部分，撤销推入操作
            
            if i >= len(target):
                break  # 如果已构建完目标数组，结束循环
        
        return res

Explore

在题解中，循环会在检测到目标数组的最后一个元素被成功处理后立即终止。这是因为一旦目标数组的所有元素都已经按顺序被加入（对应每个'Push'操作后的检查），就不再需要继续读取更多的数字或进行更多的操作。既然目标数组已完全构建，继续执行循环没有必要，因此会用`if i >= len(target): break`这行代码来检查是否所有目标元素都已处理，并据此终止循环。没有其他情况会导致提前终止，除非外部中断或异常。

如果输入的目标数组target为空，函数在进入for循环之前就会直接返回空数组。这是因为在for循环开始之前，代码中有一个检查：`if not target: return []`。这行代码会在target为空时立即返回空数组，因此for循环不会被执行。这种设计避免了不必要的迭代，提高了函数的效率。

这种首先进行'Push'然后可能执行'Pop'的策略确实在某些情况下可能导致效率上的浪费，尤其是当存在许多不需要的数字时。更优的策略可以包括先检查当前数字是否是目标数组中需要的，如果不是，则根本不执行'Push'操作，从而避免不必要的'Push'和随后的'Pop'。这样可以减少操作的次数，提高代码的执行效率。然而，这需要修改现有的算法逻辑，可能会使代码的逻辑复杂度略有增加。

当前的算法假设target数组是严格递增的并且所有元素都在1到n的范围内。如果target数组包含超出这个范围的数字或者数字不是递增的，现有算法将无法正确执行。例如，如果target包含比n大的数字，这些数字永远不会被读取，因此无法正确构建目标数组。如果数组不是递增的，给定的算法也无法处理，因为它依赖于递增顺序来逐步构建数组。在这种情况下，需要重新设计算法，以适应更广泛的输入情况。