[LeetCode] 1441. Build an Array With Stack Operations

You are given an integer array target and an integer n.
You have an empty stack with the two following operations:
“Push”: pushes an integer to the top of the stack.
“Pop”: removes the integer on the top of the stack.
You also have a stream of the integers in the range [1, n].
Use the two stack operations to make the numbers in the stack (from the bottom to the top) equal to target. You should follow the following rules:
If the stream of the integers is not empty, pick the next integer from the stream and push it to the top of the stack.
If the stack is not empty, pop the integer at the top of the stack.
If, at any moment, the elements in the stack (from the bottom to the top) are equal to target, do not read new integers from the stream and do not do more operations on the stack.
Return the stack operations needed to build target following the mentioned rules. If there are multiple valid answers, return any of them.

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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

用栈操作构建数组。

思路

思路是通过 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实现

class Solution {
    public List<String> buildArray(int[] target, int n) {
        List<String> res = new ArrayList<>();
        int i = 1;
        int j = 0;
        while (j < target.length) {
            res.add("Push");
            if (target[j] != i) {
                res.add("Pop");
            } else {
                j++;
            }
            i++;
        }
        return res;
    }
}