1441. 用栈操作构建数组 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 个数字就可以停止。

解题思路

输入：一个目标数组 target（递增），一个整数 n输出：返回构建目标数组所需的操作序列（由 "Push" 和 "Pop" 组成）

本题属于 基础栈模拟 问题。

1. 初始化变量：curr = 1，res = []，分别表示当前读取的数字和操作序列。
2. 遍历 target 中每个数字 num：
   • 如果 curr < num：说明不是目标值，执行 "Push" + "Pop" 丢弃，并递增 curr
   • 如果 curr == num：执行 "Push" 保留，并递增 curr
3. 最后返回操作序列 res。

代码实现

python

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        curr = 1           # 当前读取的数字，从 1 开始递增
        res = []           # 用于记录操作序列（Push 和 Pop）

        # 遍历 target 中的每一个目标数字
        for num in target:
            # 如果当前数字比目标小，说明这个数字不是我们想要的
            # 需要执行 Push 再 Pop，将它读入又删掉
            while curr < num:
                res.append('Push')   # 读入这个数字
                res.append('Pop')    # 马上删除（因为不是 target 中的）
                curr += 1            # 准备读下一个数字
            
            # 当前数字等于目标数字，直接保留（Push）
            res.append('Push')
            curr += 1                # 移动到下一个数字
        
        return res                   # 返回完整的操作序列

javascript

const buildArray = function(target, n) {
    let curr = 1;
    const ans = [];

    for (let num of target) {
        while (curr < num) {
            ans.push('Push');
            ans.push('Pop');
            curr ++;
        }

        ans.push('Push');
        curr ++;
    }

    return ans;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

1441 国际版

1441 中文版