图解LeetCode——1441. 用栈操作构建数组（难度：中等）

一、题目

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

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

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

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

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

二、示例

2.1> 示例 1：

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

2.2> 示例 2：

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

2.3> 示例 3：

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

提示：

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

三、解题思路

根据题目描述可以知道，list集合是严格递增的，即： list = { 1 , 2 , 3 ..., n }，而且target数组也是严格递增的，因为我们最终的结果是要获取拼装成target的“动作”（“Push”/“Pop”）集合，所以，我们只需要遍历targe数组，使其与递增的num进行对比，因为num的初始值为1，每次对比num都执行加1操作，所以在最终遍历之后，它的值就是1,2,3……递增的，可以代表题目中锁描述的集合list。

创建用于最终结果返回的集合List<String> result；那么，当target[i]等于num的时候，则向result中插入“Push”字符串；当target[i]不等于num的时候，则向result中插入“Push”和“Pop”字符串；依次类推，当遍历完target数组后，将最终的结果result返回即可。具体操作如下图所示：

其实根据题意描述，我们要拼装出来能够组成target的动作集合，那么默认来说，就一定能够通过list集合拼装成target，所以，本题中的第二个参数int n，其实没什么用处了。

四、代码实现

class Solution {
    public List<String> buildArray(int[] target, int n) {
        List<String> result = new ArrayList();
        int num = 1;
        for (int item: target) {
            while (item != num) {
                result.add("Push");
                result.add("Pop");
                num++;
            }
            result.add("Push");
            num++;
        }
        return result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」