関小君刷题记

题目大意：

用栈操作构建数组

给你一个目标数组 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 个数字就可以停止。

示例 4：

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

提示：

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1441

解题思路分析：

这道题没有什么难度，虽然题目说的是用栈Stack来构建数组，但实际上解题时我们并不需要真正的用到，只要做到心中有栈即可。

1. 定义一个num变量，代表当前list中的当前数字。
2. 循环目标数组中的每个数，如果当前数字等于num，将num直接Push进栈即可，此时输出Push。同时num加一（移动到list中下一个元素）。
3. 如果当前数字不等于num（因为list与数组都是严格递增，因此当前数字一定小于num），那我们需要将num先Push到栈，再马上Pop出栈，这样栈中的元素没有发生变化，但是List中的元素却向后位移了一位。重复此操作，直到当前数字等于num为止。
4. 注意，每Push一次，实际上都是从list中取出了一个数字，这时num都要做加一操作。

实现代码：

public List<String> buildArray(int[] target, int n) {
    List<String> res = new ArrayList<>();
    int num=1; // list中当前数字
    for(int i=0;i<target.length;i++){
        if(num==target[i]){
            res.add("Push");
            num++;
        }else{
            while(num<target[i]){
                res.add("Push");
                res.add("Pop");
                num++;
            }
            res.add("Push");
            num++;
        }
    }
    return res;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Build an Array With Stack Operations.

Memory Usage: 39.5 MB, less than 100.00% of Java online submissions for Build an Array With Stack Operations.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1441-build-an-array-with-stack-operations-解题思路分析/