Skip to content

注：Q1、Q2来自力扣学习计划“编程基础 0 到 1”中的章节。 1769689360197

Q1. 用栈操作构建数组

给你一个数组 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 <= 100\)
  • \(1 <= n <= 100\)
  • \(1 <= target[i] <= n\)
  • target 严格递增

思路

我们可以使用一个指针 j 来遍历 target 数组，同时使用一个循环从 1 遍历到 n。对于每个数字 i：

  1. 我们首先执行一个 "Push" 操作，将 i 推入栈
  2. 然后检查 i 是否等于 target[j]:如果相等，说明我们需要保留这个数字，移动指针 j 到下一个位置;如果不相等，说明这个数字不在 target 中，我们需要执行一个 "Pop" 操作，将其从栈中移除。
  3. 当指针 j 达到 target 数组的长度时，说明我们已经构建完成，可以停止操作。

代码实现

class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        vector<string> res;
        int j = 0;
        for(int i = 1;i<=n&& j<target.size();i++){
            res.push_back("Push");
            if(i==target[j]){
                j++;
            }else res.push_back("Pop");
        }
        return res;
    }
};