1441. 用栈操作构建数组
来源第 188 场周赛 Q1难度中等分数1180
题目描述
给你一个数组 target 和一个整数 n。
给你一个空栈和两种操作:
"Push":将一个整数加到栈顶。"Pop":从栈顶删除一个整数。
同时给定一个范围 [1, n] 中的整数流。
使用两个栈操作使栈中的数字(从底部到顶部)等于 target。你应该遵循以下规则:
- 如果整数流不为空,从流中选取下一个整数并将其推送到栈顶。
- 如果栈不为空,弹出栈顶的整数。
- 如果,在任何时刻,栈中的元素(从底部到顶部)等于
target,则不要从流中读取新的整数,也不要对栈进行更多操作。
请返回遵循上述规则构建 target 所用的操作序列。如果存在多个合法答案,返回 任一 即可。
示例 1:
输入:target = [1,3], n = 3 输出:["Push","Push","Pop","Push"] 解释:一开始栈为空。最后一个元素是栈顶。 从流中读取 1 并推入数组。s = [1]。 从流中读取 2 并推入数组。s = [1,2]。 从栈顶删除整数。s = [1]。 从流中读取 3 并推入数组。s = [1,3]。
示例 2:
输入:target = [1,2,3], n = 3 输出:["Push","Push","Push"] 解释:一开始栈为空。最后一个元素是栈顶。 从流中读取 1 并推入数组。s = [1]。 从流中读取 2 并推入数组。s = [1,2]。 从流中读取 3 并推入数组。s = [1,2,3]。
示例 3:
输入:target = [1,2], n = 4 输出:["Push","Push"] 解释:一开始栈为空。最后一个元素是栈顶。 从流中读取 1 并推入数组。s = [1]。 从流中读取 2 并推入数组。s = [1,2]。 由于栈(从底部到顶部)等于 target,我们停止栈操作。 从流中读取整数 3 的答案不被接受。
提示:
1 <= target.length <= 1001 <= n <= 1001 <= target[i] <= ntarget严格递增
解法
方法一:模拟
思考
流是 \(1,2,\ldots,n\), \(\textit{target}\) 严格递增。对 \(\textit{target}\) 中未出现的数必须 \(\textit{Push}\) 再立刻 \(\textit{Pop}\),出现的数只 \(\textit{Push}\)。
用指针 \(\textit{cur}\) 表示下一个读入的数,对每个目标值 \(x\),先把空隙填成 Push/Pop,再 Push \(x\)。 \(n\le 100\),模拟即可。
我们定义一个变量 \(\textit{cur}\) 表示当前待读取的数字,初始时 \(\textit{cur} = 1\),用一个数组 \(\textit{ans}\) 存储答案。
接下来,我们遍历数组 \(\textit{target}\) 中的每个数字 \(x\):
- 如果 \(\textit{cur} < x\),我们将 \(\textit{Push}\) 和 \(\textit{Pop}\) 依次加入答案,直到 \(\textit{cur} = x\);
- 然后我们将 \(\textit{Push}\) 加入答案,表示读取数字 \(x\);
- 接着,我们将 \(\textit{cur}\) 加一,继续处理下一个数字。
遍历结束后,返回答案数组即可。
时间复杂度 \(O(n)\),空间复杂度 \(O(1)\)。其中 \(n\) 是数组 \(\textit{target}\) 的长度。
1 2 3 4 5 6 7 8 9 10 11 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
1 2 3 4 5 6 7 8 9 10 11 | |
1 2 3 4 5 6 7 8 9 10 11 12 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |