Build an Array with Stack Operations in Java

给定一个整数 数组 "arr" 和一个 整数 k。我们有一个空的 栈，以及以下两个操作：“入栈”（Push）和“出栈”（Pop）。我们还有一个整数流，其范围为 [1, k]。使用上述两个栈操作，使栈中的数字（从底部到顶部）等于目标数组。我们应该遵循以下规则：

• 如果整数流不为空，则从流中取出下一个整数并将其放入栈顶。
• 如果栈不为空，则弹出栈顶的整数。
• 如果在任何时候，栈中的元素（从底部到顶部）等于目标数组，则不要从流中读取新的整数，也不要对栈执行任何其他操作。

根据上述规则，返回构建目标数组所需的栈操作。如果有多个有效答案，可以选择其中任何一个。

示例 1

输入: arr = {1, 4, 5, 6, 7}, n = 7

输出: [Push, Push, Pop, Push, Pop, Push, Push, Push, Push]

解释: 上面的输出显示了使用栈操作将元素插入数组的过程。我们可以插入7个元素到数组中，但插入元素的数组应该与目标数组相同。每当新数组与目标数组匹配时，就会返回栈操作过程。

示例 2

输入: arr = {2, 4, 6, 8, 10}, n = 10

输出: [Push, Pop, Push, Push, Pop, Push, Push, Pop, Push, Push, Pop, Push, Push, Pop, Push]

解释: 上面的输出显示了使用栈操作将元素插入数组的过程。我们可以插入10个元素到数组中，但插入元素的数组应该与目标数组相同。每当新数组与目标数组匹配时，就会返回栈操作过程。

示例 3

输入: arr = {1, 3, 5, 7, 9}, n = 12

输出: [Push, Push, Pop, Push, Push, Pop, Push, Push, Pop, Push, Push, Pop, Push]

解释: 上面的输出显示了使用栈操作将元素插入数组的过程。我们可以插入12个元素到数组中，但当我们到达元素“9”时，插入元素的数组与目标数组相同。每当新数组与目标数组匹配时，就会返回栈操作过程。

方法：使用数组

算法

步骤 1: 创建一个目标数组 arr[] 来存储数字集合，并创建一个变量 ‘k’ 来存储一个整数。

步骤 2: 创建一个空列表来保存栈操作。

步骤 3: 设置一个指针（position）来跟踪目标数组中的元素。

步骤 4: 对于从 1 到 k 的每个数字 h

步骤 4.1: 检查 ‘h’ 是否是目标数组的最后一个元素。

步骤 4.1.2: 如果是“是”，则将“Push”添加到列表中并终止该过程。

步骤 4.2: 检查 ‘h’ 是否不在目标数组中。

步骤 4.2.1: 如果 ‘h’ 与当前目标元素不匹配，则添加“Push”，然后添加“Pop”。

步骤 4.3: 检查 ‘h’ 是否与目标数组中的下一个条目匹配。

步骤 4.3.1: 如果是“是”，则转到目标数组中的下一个位置并添加“Push”。

步骤 5: 处理完所有数字后，返回包含栈操作序列的列表。

让我们在 Java 程序中实现上述步骤。

输出

 
The sequence of stack operations is: [Push, Push, Pop, Push, Pop, Push, Pop, Push, 
Push, Pop, Push, Pop, Push, Push]
The sequence of stack operations is: [Push, Pop, Push, Push, Pop, Push, Pop, Push, Push, Pop, Push, Push]
The sequence of stack operations is: [Push, Push, Push, Push]   

复杂度分析

时间复杂度

时间复杂度为 O(k)，因为循环从 1 迭代到 k，在每一步执行“Push”或“Pop”操作。位置变量保证了“arr”中的元素会按顺序被验证，避免了冗余的比较。在最佳情况下，当“arr”的最后一个元素很小时，循环会提前退出，导致复杂度为 O(min(k, arr[arr.length - 1])。

空间复杂度

空间复杂度为 O(k)，因为输出列表最多可以包含 k 个栈操作。在最坏的情况下，从 1 到 k 的每个整数可能都需要“Push”和“Pop”操作，导致空间线性增长。除了列表之外，只使用了几个整数变量，它们占用 O(1) 空间，对总复杂度影响很小。

方法：使用模拟

算法

步骤 1: 创建一个目标数组“arr”来存储数字集合，并创建一个变量‘k’来存储一个整数。

步骤 2: 创建一个空列表来存储栈操作。

步骤 3: 设置一个指针（p）来跟踪目标数组中的位置。

步骤 4: 从插入值（in）1 开始。

步骤 5: 将当前的插入值（in）与目标数组中索引为 p 的元素进行比较。

步骤 5.1: 如果值匹配，则将“Push”添加到列表中，并转到下一个目标元素。

步骤 5.2: 如果它们不匹配，则组合“Push”和“Pop”来模拟一个被忽略的值。

步骤 5.3: 继续增加插入值，直到处理完目标数组的所有元素。

步骤 6: 返回最终列表，其中包含构建目标数组所需的“Push”和“Pop”操作序列。

让我们在 Java 程序中实现上述步骤。

输出

 
The sequence of stack operations is: [Push, Push, Pop, Push, Pop, Push, Pop, Push, Push]
The sequence of stack operations is: [Push, Pop, Push, Push, Push, Pop, Push, Push]
The sequence of stack operations is: [Push, Push, Push]   

复杂度分析

时间复杂度

时间复杂度为 O(k)，因为 循环 从 1 迭代到 k，每一步都涉及“Push”或“Push”和“Pop”操作。在最坏的情况下，处理从 1 到 k 的所有数字，结果是 O(k) 操作。当“arr”中的元素与当前数字匹配时，指针‘p’才会移动，这确保了“arr”中的每个元素都按顺序被检查。

空间复杂度

空间复杂度为 O(k)，因为输出列表包含最多 ‘k’ 个条目的栈操作。在最坏的情况下，从 1 到 k 的每个数字可能都需要“Push”和“Pop”操作，导致空间占用线性增长。除了列表之外，只使用了几个整数变量，它们需要 O(1) 空间，并且对总复杂度影响很小。

方法：使用栈

算法

步骤 1: 创建一个目标数组“arr”来存储数字集合，并创建一个变量‘k’来存储一个整数。

步骤 2: 设置一个指针来跟踪当前数字，从 1 开始。

步骤 3: 创建一个空列表来保存栈操作。

步骤 4: 将目标数组中的每个元素与其对应的当前指针进行比较。

步骤 4.1: 如果当前数字与目标元素匹配，则将“Push”添加到列表中，并转到下一个元素。

步骤 4.2: 如果当前值小于目标元素

步骤 4.2.1: 重复“Push”操作，直到达到目标。

步骤 4.2.2: 跟踪多余的推送次数，并使用等效的“Pop”操作来删除不需要的组件。

步骤 4.2.3: 最后，添加“Push”来插入正确的元素。

步骤 4.3: 对目标数组中的每个元素重复此过程。

步骤 5: 返回包含构建目标数组所需的“Push”和“Pop”操作的列表。

让我们在 Java 程序中实现上述步骤。

输出

 
The sequence of stack operations is: [Push, Pop, Push, Push, Pop, Push, Push, Pop, Push]
The sequence of stack operations is: [Push, Push, Push, Push, Push, Pop, Pop, Pop, Pop, Push, Push]
The sequence of stack operations is: [Push, Push, Push, Push, Pop, Pop, Pop, Push]   

复杂度分析

时间复杂度

时间复杂度为 O(b + c)，其中 b 是目标数组的大小，c 是 1 到 k 之间跳过的元素数量。在最坏的情况下，考虑从 1 到 k 的所有元素，复杂度变为 O(k)。序列中的每个元素都会导致两种操作之一：Push 或 Pop，总共最多 2k 次操作。

空间复杂度

空间复杂度为 O(b + c)，其中 b 是目标数组的大小，c 是跳过的元素数量。在最坏的情况下，列表存储的操作不超过 2k 次，导致 O(k) 的空间复杂度。除此之外，几个整数变量（p 和 pop）需要 O(1) 空间。由于输出列表占用了大部分空间，因此总空间复杂度保持为 O(k)。

方法：使用迭代器

算法

步骤 1: 创建一个空的 目标数组 ‘arr’，它将包含数字集合，以及一个整数 ‘k’。

步骤 2. 创建一个空集合，其中包含目标数组的所有元素。

步骤 3: 将目标数组中的每个元素插入到该集合中。

步骤 4: 创建一个空列表来存储栈操作序列。

步骤 5: 构建一个循环，该循环从 1 开始迭代每个数字，直到目标数组的最后一个条目。

步骤 6: 现在，对于序列中的每个数字，将“Push”添加到操作列表中。

1. 使用哈希集检查该数字是否存在于目标数组中。
2. 如果元素不在集合中，则在“Push”之后执行“Pop”。
3. 重复此过程，直到达到所需的最后一个元素。

步骤 7: 现在，返回列表，其中包含构建目标数组所需的栈操作序列。

让我们在 Java 程序中实现上述步骤。

输出

 
The sequence of stack operations is: [Push, Push, Pop, Push, Push, Pop, Push, Push]
The sequence of stack operations is: [Push, Push, Push, Push, Pop, Push, Pop, Push, Pop, Push, Push]
The sequence of stack operations is: [Push, Push, Push, Push, Push]   

复杂度分析

时间复杂度

时间复杂度为 O(p + s)，其中 ‘p’ 表示 ‘arr’ 的长度，‘s’ 表示 ‘arr’ 中的最大值。HashSet 在 O(p) 时间内创建，并且循环运行 O(s) 次，其中包含 Push 和 Pop 等常数时间操作。如果包含从 1 到 k 的所有数字，则复杂度降至 O(k)，但如果“arr”是稀疏的，则 O(p) 是一个更接近的估计。

空间复杂度

空间复杂度为 O(p + s)，其中 p 是“arr”的大小，s 是其最大值。来自“arr”中元素的 HashSet 需要 O(p) 空间，并且在最坏的情况下，输出列表包含 2s 次操作，需要 O(s) 空间。总空间利用率为 O(p + s)，由于 s 最多等于 k，因此减少到 O(p + k)。