2899. 上一个遍历的整数

February 25, 2026 · View on GitHub

English Version

题目描述

给你一个整数数组 nums ，其中 nums[i] 要么是一个正整数，要么是 -1 。我们需要为每个 -1 找到相应的正整数，我们称之为最后访问的整数。

为了达到这个目标，定义两个空数组：seen 和 ans。

从数组 nums 的头部开始遍历。

如果遇到正整数，把它添加到 seen 的头部。
如果遇到 -1，则设 k 是到目前为止看到的连续 -1 的数目(包括当前 -1)，
- 如果 k 小于等于 seen 的长度，把 seen 的第 k 个元素添加到 ans。
- 如果 k 严格大于 seen 的长度，把 -1 添加到 ans。

请你返回数组 ans。

示例 1：

输入：nums = [1,2,-1,-1,-1]
输出：[2,1,-1]
解释： 开始时 seen = [] 且 ans = []。
1.处理 nums[0]：nums 中的第一个元素是 1。我们将其放在 seen 的前面。现在，seen == [1]。
2.处理 nums[1]：下一个元素是 2。我们将其放在 seen 的前面。现在，seen == [2, 1]。
3.处理 nums[2]：下一个元素是 -1。这是 -1 的第一次出现，所以 k == 1。我们找到 seen 中的第一个元素，把 2 添加到 ans。现在，ans == [2]。
4.处理 nums[3]：又一个 -1。这是 -1 的第二次出现，所以 k == 2。seen 中的第二个元素是 1，所以我们把 1 添加到 ans。现在，ans == [2, 1]。
5.处理 nums[4]：又一个 -1。第三次出现，让 k = 3。然而，seen 中只有两个元素（[2, 1]）。因为 k 比 seen 中的元素数量更大，我们把 -1 添加到 ans。最终，ans == [2, 1, -1]。

示例 2：

输入：nums = [1,-1,2,-1,-1]
输出：[1,2,1]
解释： 开始时 seen = [] 且 ans = []。
1.处理 nums[0]：nums 中的第一个元素是 1。我们将其放在 seen 的前面。现在，seen == [1]。
2.处理 nums[1]：下一个元素是 -1。这是 -1 的第一次出现，所以 k == 1。我们找到 seen 中的第一个元素，即 1。把 1 添加到 ans。现在，ans == [1]。
3.处理 nums[2]：下一个元素是 2。我们将其放在 seen 的前面。现在，seen == [2, 1]。
4.处理 nums[3]：下一个元素是 -1。这个 -1 与 第一个 -1 不连续，因为中间有个 2。因此，k 重置为 1。seen 中的第一个元素是 2，所以我们把 2 添加到 ans。现在，ans == [1, 2]。
5.处理 nums[4]：又一个 -1。它与前一个 -1 相邻，所以 k == 2。seen 中的第 2 个元素是 1。把 1 添加到 ans。最终，ans == [1, 2, 1]。

提示：

1 <= nums.length <= 100
nums[i] == -1 或 1 <= nums[i] <= 100

解法

方法一：模拟

我们直接根据题意模拟即可。

定义一个数组 $\textit{seen}$ 来存储我们看到的正整数，定义一个数组 $\textit{ans}$ 来存储答案。我们还需要一个变量 $k$ 来记录连续出现的 $-1$ 的数量。

我们遍历数组 $\textit{nums}$ ：

如果当前元素 $x = -1$ ，我们将 $k$ 加 1。如果 $k$ 大于 $\textit{seen}$ 的长度，我们在 $\textit{ans}$ 中添加 $-1$ ；否则，我们在 $\textit{ans}$ 中添加 $\textit{seen}$ 的倒数第 $k$ 个元素。
如果当前元素 $x$ 是一个正整数，我们将 $k$ 重置为 0，并将 $x$ 添加到 $\textit{seen}$ 的末尾。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。

Python3

class Solution:
    def lastVisitedIntegers(self, nums: List[int]) -> List[int]:
        seen = []
        ans = []
        k = 0
        for x in nums:
            if x == -1:
                k += 1
                ans.append(-1 if k > len(seen) else seen[-k])
            else:
                k = 0
                seen.append(x)
        return ans

Java

class Solution {
    public List<Integer> lastVisitedIntegers(int[] nums) {
        List<Integer> seen = new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        int k = 0;
        for (int x : nums) {
            if (x == -1) {
                if (++k > seen.size()) {
                    ans.add(-1);
                } else {
                    ans.add(seen.get(seen.size() - k));
                }
            } else {
                k = 0;
                seen.add(x);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> lastVisitedIntegers(vector<int>& nums) {
        vector<int> seen;
        vector<int> ans;
        int k = 0;

        for (int x : nums) {
            if (x == -1) {
                if (++k > seen.size()) {
                    ans.push_back(-1);
                } else {
                    ans.push_back(seen[seen.size() - k]);
                }
            } else {
                k = 0;
                seen.push_back(x);
            }
        }

        return ans;
    }
};

Go

func lastVisitedIntegers(nums []int) []int {
	seen := []int{}
	ans := []int{}
	k := 0

	for _, x := range nums {
		if x == -1 {
			k++
			if k > len(seen) {
				ans = append(ans, -1)
			} else {
				ans = append(ans, seen[len(seen)-k])
			}
		} else {
			k = 0
			seen = append(seen, x)
		}
	}

	return ans
}

TypeScript

function lastVisitedIntegers(nums: number[]): number[] {
    const seen: number[] = [];
    const ans: number[] = [];
    let k = 0;

    for (const x of nums) {
        if (x === -1) {
            if (++k > seen.length) {
                ans.push(-1);
            } else {
                ans.push(seen.at(-k)!);
            }
        } else {
            k = 0;
            seen.push(x);
        }
    }

    return ans;
}

Rust

impl Solution {
    pub fn last_visited_integers(nums: Vec<i32>) -> Vec<i32> {
        let mut seen: Vec<i32> = Vec::new();
        let mut ans: Vec<i32> = Vec::new();
        let mut k: i32 = 0;

        for x in nums {
            if x == -1 {
                k += 1;
                if k as usize > seen.len() {
                    ans.push(-1);
                } else {
                    ans.push(seen[seen.len() - k as usize]);
                }
            } else {
                k = 0;
                seen.push(x);
            }
        }

        ans
    }
}