What is the time complexity of this problem?

The time complexity of this problem is O(n), where n is the length of the input array. We iterate through the array once.

How do I handle a -1 without a previous positive integer?

If -1 occurs without a preceding positive integer, the problem would typically assume the behavior as if there’s no valid positive integer to assign, depending on the problem's constraints.

What is the purpose of the `seen` array?

The `seen` array stores all encountered positive integers, acting as a stack from which we can pop values when a -1 is encountered.

Is there a way to optimize space usage?

Space optimization can be achieved by using a stack instead of an array, but in this case, the solution with an array is efficient enough given the problem constraints.

What does 'last visited integer' mean in the context of this problem?

The 'last visited integer' is the most recent positive integer encountered before a -1 in the array. It's analogous to the most recent value in a stack.

#2899

Easy

auto_awesome数组·模拟

LeetCode 题解工作台

上一个遍历的整数

给你一个整数数组 nums ，其中 nums[i] 要么是一个正整数，要么是 -1 。我们需要为每个 -1 找到相应的正整数，我们称之为最后访问的整数。为了达到这个目标，定义两个空数组： seen 和 ans 。从数组 nums 的头部开始遍历。如果遇到正整数，把它添加到 seen 的头部 …

数组模拟

题目描述

给你一个整数数组 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

lightbulb

解题思路

方法一：模拟

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

定义一个数组 $\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}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ensure the candidate can correctly simulate stack behavior by popping from a list.
question_mark
Look for understanding of stack simulation in an array context.
question_mark
Observe if the candidate can properly handle the time and space complexities in array manipulation problems.

warning

常见陷阱

外企场景

error
Forgetting to handle the case where no positive integers have been encountered before a -1.
error
Improperly managing the state of the `seen` array between iterations.
error
Using unnecessary auxiliary arrays or overcomplicating the solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider handling edge cases with all positive integers or all -1s.
arrow_right_alt
Try solving the problem with additional constraints on the array size or values.
arrow_right_alt
Consider if a recursive solution could replace the iterative stack simulation.

help

常见问题

外企场景

继续练习

#2946 循环移位后的矩阵相似检查 #2960 统计已测试设备 #2961 双模幂运算