栈、顺序遍历，为可变数组添加元素，2 解法求解《1441. 用栈操作构建数组》
例题
1441. 用栈操作构建数组
给你一个数组 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 个数字就可以停止。
提示：
1 <= target.length <= 100
1 <= n <= 100
1 <= target[i] <= n
target 严格递增
答案
栈
不在 target 数组的数字：先推入，再弹出
var buildArray = function(target, n) {
const st = [], m = target.length, r = []
for (let i = 0, j = 1; i < m; i++) {
while (j < target[i]) st.push(j++), r.push('Push')
while (st.length > 0 && (i === 0 || i > 0 && st[st.length - 1] > target[i - 1])) st.pop(), r.push('Pop')
st.push(j++), r.push('Push')
}
return r
};顺序遍历
不在 target 数组的数字：边推入，边弹出
var buildArray = function(target, n) {
const r = [], m = target.length
for (let i = 0, j = 0; i < m; i++) {
while (++j < target[i]) r.push('Push', 'Pop')
r.push('Push')
}
return r
};function buildArray(target: number[], n: number): string[] {
const m = target.length, r = []
for (let i = 0, j = 0; i < m; i++) {
while (++j < target[i]) r.push('Push', 'Pop')
r.push('Push')
}
return r
};class Solution {
function buildArray($target, $n) {
$r = [];
$m = count($target);
for ($i = 0, $j = 0; $i < $m; $i++) {
while (++$j < $target[$i]) array_push($r, 'Push', 'Pop');
array_push($r, 'Push');
}
return $r;
}
}func buildArray(target []int, n int) []string {
r, j := []string{}, 1
for _, c := range target {
for j < c {
r = append(r, "Push", "Pop")
j++
}
r = append(r, "Push")
j++
}
return r
}class Solution {
public List<String> buildArray(int[] target, int n) {
List<String> r = new ArrayList<String>();
int m = target.length;
for (int i = 0, j = 0; i < m; i++) {
while (++j < target[i]) {
r.add("Push");
r.add("Pop");
}
r.add("Push");
}
return r;
}
}public class Solution {
public IList<string> BuildArray(int[] target, int n) {
int m = target.Length;
IList<string> r = new List<string>();
for (int i = 0, j = 0; i < m; i++) {
while (++j < target[i]) {
r.Add("Push");
r.Add("Pop");
}
r.Add("Push");
}
return r;
}
}char ** buildArray(int* target, int targetSize, int n, int* returnSize){
char** r = malloc(sizeof(char*) * (n << 1));
int pos = 0;
for (int i = 0, j = 0; i < targetSize; i++) {
while (++j < target[i]) r[pos++] = "Push", r[pos++] = "Pop";
r[pos++] = "Push";
}
*returnSize = pos;
return r;
}class Solution {
public:
vector<string> buildArray(vector<int>& target, int n) {
vector<string> r;
for (int i = 0, j = 0, m = target.size(); i < m; i++) {
while (++j < target[i]) r.emplace_back("Push"), r.emplace_back("Pop");
r.emplace_back("Push");
}
return r;
}
};class Solution:
def buildArray(self, target: List[int], n: int) -> List[str]:
r, j = [], 1
for _, c in enumerate(target):
while j < c:
r.append("Push")
r.append("Pop")
j += 1
r.append("Push")
j += 1
return r