Medium

题目描述

给你一个整数数组 target 和一个整数 n。

你有一个空栈，支持以下两种操作：

  • “Push”：将一个整数推入栈顶
  • “Pop”：移除栈顶的整数

你还有一个整数流，包含从 1 到 n 的所有整数。

使用栈操作使栈中的数字（从栈底到栈顶）等于 target。你需要遵循以下规则：

  • 如果整数流不为空，从流中取出下一个整数并将其推入栈顶
  • 如果栈不为空，可以弹出栈顶的整数
  • 如果在任何时候，栈中的元素（从栈底到栈顶）等于 target，则停止从流中读取整数，也不再对栈进行操作

返回构建 target 所需的栈操作序列。如果有多个有效答案，返回其中任何一个。

示例 1：

输入：target = [1,3], n = 3
输出：["Push","Push","Pop","Push"]
解释：
初始时栈 s 为空。栈顶是最后一个元素。
从流中读取 1 并推入栈。s = [1]。
从流中读取 2 并推入栈。s = [1,2]。
弹出栈顶的整数。s = [1]。
从流中读取 3 并推入栈。s = [1,3]。

示例 2：

输入：target = [1,2,3], n = 3
输出：["Push","Push","Push"]

示例 3：

输入：target = [1,2], n = 4
输出：["Push","Push"]

约束：

  • 1 <= target.length <= 100
  • 1 <= n <= 100
  • 1 <= target[i] <= n
  • target 严格递增

提示：

  • 对于要保留在目标数组中的数字使用 “Push”，对于要丢弃的数字使用 [“Push”, “Pop”]

解题思路

这道题的核心思路是模拟栈操作的过程。

我们需要从数字流 [1, 2, 3, ..., n] 中依次取数字，目标是让栈底到栈顶的元素序列等于 target。

解题思路：

  1. 逐一处理数字流：从 1 开始遍历到 n（或直到构建完成目标数组）
  2. 判断当前数字是否需要：
    • 如果当前数字在 target 中，执行 “Push” 操作
    • 如果当前数字不在 target 中，执行 “Push” 后立即执行 “Pop”（相当于跳过这个数字）
  3. 优化判断：由于 target 是严格递增的，我们可以用一个指针来跟踪当前需要匹配的目标元素，避免重复搜索

具体算法：

  • 使用指针 targetIndex 指向当前要匹配的 target 元素
  • 遍历数字流中的每个数字 current：
    • 如果 current 等于 target[targetIndex]，添加 “Push” 并移动指针
    • 否则，添加 “Push” 和 “Pop”
  • 当 targetIndex 到达 target 长度时停止

这种方法的时间复杂度是 O(target中最大值)，空间复杂度是 O(1)（不考虑结果数组）。

代码实现

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

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        result = []
        target_index = 0
        current = 1
        
        while target_index < len(target) and current <= n:
            if current == target[target_index]:
                result.append("Push")
                target_index += 1
            else:
                result.append("Push")
                result.append("Pop")
            current += 1
            
        return result

public class Solution {
    public IList<string> BuildArray(int[] target, int n) {
        IList<string> result = new List<string>();
        int targetIndex = 0;
        int current = 1;
        
        while (targetIndex < target.Length && current <= n) {
            if (current == target[targetIndex]) {
                result.Add("Push");
                targetIndex++;
            } else {
                result.Add("Push");
                result.Add("Pop");
            }
            current++;
        }
        
        return result;
    }
}

var buildArray = function(target, n) {
    const result = [];
    let targetIndex = 0;
    
    for (let i = 1; i <= n && targetIndex < target.length; i++) {
        result.push("Push");
        
        if (target[targetIndex] === i) {
            targetIndex++;
        } else {
            result.push("Pop");
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
构建操作序列O(max(target))O(1)

说明：

  • 时间复杂度：O(max(target))，需要遍历从 1 到 target 最大值的所有数字
  • 空间复杂度：O(1)，只使用了常量级别的额外空间（不考虑结果数组的存储空间）

相关题目