[LeetCode] 1441. Build an Array With Stack Operations

Given an array target and an integer n. In each iteration, you will read a number from list = {1,2,3..., n}.

Build the target array using the following operations:

Push: Read a new element from the beginning list, and push it in the array.
Pop: delete the last element of the array.
If the target array is already built, stop reading more elements.

You are guaranteed that the target array is strictly increasing, only containing numbers between 1 to n inclusive.

Return the operations to build the target array.

You are guaranteed that the answer is unique.

Example 1:

Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: 
Read number 1 and automatically push in the array -> [1]
Read number 2 and automatically push in the array then Pop it -> [1]
Read number 3 and automatically push in the array -> [1,3]

Example 2:

Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]

Example 3:

Input: target = [1,2], n = 4
Output: ["Push","Push"]
Explanation: You only need to read the first 2 numbers and stop.

Example 4:

Input: target = [2,3,4], n = 4
Output: ["Push","Pop","Push","Push","Push"]

Constraints:

1 <= target.length <= 100
1 <= target[i] <= 100
1 <= n <= 100
target is strictly increasing.

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

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

Push：从 list 中读取一个新元素，并将其推入数组中。

Pop：删除数组中的最后一个元素。如果目标数组构建完成，就停止读取更多元素。

题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。请返回构建目标数组所用的操作序列。题目数据保证答案是唯一的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/build-an-array-with-stack-operations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个题美版downvote多于upvote是有原因的，题意的解释很不清楚。其实题意是给你一个数字N，每次跑这个buildArray()函数的时候，会按顺序从1到N给你这些数字，请你输出的是stack的一些操作，最后使得任何人执行了你在res里记录的操作，可以得到跟target一样的数组。

思路是通过stack的操作，返回应该做的操作。举个例子好了，因为最后的结果是从1开始判断的，所以需要从1到N遍历每个数字，如果当前数字需要，你就会知道当前这个数字是需要push的；如果当前数字不需要，因为需要模拟stack的操作，所以需要push再pop。

我看到美版讨论里面有个人问怎么保证答案是唯一的，他给出了这么个例子，

target = [3,4], n = 4

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

他在问既然结果是3，4，到底应该是可以连续push呢还是不能有连续的操作。按照题意，因为target的长度是固定的，所以如果你额外多push了东西，数组是会越界的，所以不能这么做，只能在发觉当前这个数字是不需要的时候立马就pop出来。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public List<String> buildArray(int[] target, int n) {
 3         List<String> res = new ArrayList<>();
 4         int pos = 0;
 5         for (int i = 1; i <= n; i++) {
 6             if (target[pos] == i) {
 7                 res.add("Push");
 8                 pos++;
 9                 if (pos >= target.length) {
10                     break;
11                 }
12             } else {
13                 res.add("Push");
14                 res.add("Pop");
15             }
16         }
17         return res;
18     }
19 }

LeetCode 题目总结

[LeetCode] 1441. Build an Array With Stack Operations

推荐阅读