上一个遍历的整数

难度: Easy

给你一个整数数组 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 == [2, 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

Submission

运行时间: 27 ms

内存: 15.9 MB

class Solution:
    def lastVisitedIntegers(self, nums: List[int]) -> List[int]:
        res = []
        pos = []
        cnt = 0
        for i in nums:
            if i > 0:
                cnt = 0
                pos.append(i)
            else:
                cnt += 1
                if len(pos) >= cnt:
                    res.append(pos[len(pos) - cnt])
                else:
                    res.append(-1)
        return res

Explain

题解的思路是使用一个数组pos来记录遇到的正整数，使用一个计数器cnt来记录连续的-1的个数。遍历输入数组nums，当遇到正整数时，将其添加到pos数组的末尾，并重置计数器cnt为0。当遇到-1时，增加计数器cnt的值，然后检查pos数组的长度是否大于等于cnt。如果是，说明存在足够的正整数，将pos数组中倒数第cnt个元素添加到结果数组res中。如果不是，说明没有足够的正整数，将-1添加到结果数组res中。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def lastVisitedIntegers(self, nums: List[int]) -> List[int]:
        res = []  # 结果数组
        pos = []  # 存储遇到的正整数
        cnt = 0  # 连续-1的计数器
        for i in nums:
            if i > 0:
                cnt = 0  # 遇到正整数，重置计数器
                pos.append(i)  # 将正整数添加到pos数组
            else:
                cnt += 1  # 遇到-1，计数器加1
                if len(pos) >= cnt:
                    res.append(pos[-cnt])  # pos中有足够的正整数，添加到结果数组
                else:
                    res.append(-1)  # pos中没有足够的正整数，添加-1到结果数组
        return res

Explore

是的，题解中的逻辑确实需要频繁地检索数组pos的最后一部分元素。虽然数组（List）可以有效地支持这一操作，因为在数组中访问任何位置的元素的时间复杂度都是O(1)，但如果考虑到其他可能的操作如动态插入或删除，则可以考虑使用双端队列（deque）。双端队列支持在两端快速添加和删除元素，且访问任一端的元素也仅需O(1)时间复杂度。对于本题的需求，使用数组已足够高效，因为只需要在数组末尾添加元素并检索末尾的元素。

数组访问可能引发越界错误，特别是当尝试访问不存在的元素时。在题解中，通过检查数组pos的长度是否大于等于cnt来避免越界访问。这是因为我们只有在确认数组长度足以支持当前的-1计数（即存在足够多的之前存储的正整数），才尝试访问数组中的特定元素。确保安全地访问数组元素的关键是在访问前总是进行长度检查。

虽然理论上一旦连续的-1数目大于已记录的正整数数目，后续的-1也无法匹配任何正整数，但我们不能提前终止循环。这是因为循环中还可能遇到新的正整数，这些正整数需要被添加到pos数组中以用于之后可能的-1匹配。因此，不管-1的个数是否已经超过了pos数组的长度，我们都必须继续遍历整个输入数组以保证所有正整数都能被正确处理。

根据题解的逻辑，pos数组在整个处理过程中会一直积累元素，不会被清空。这是因为每个遇到的正整数都可能在未来被用来作为-1的匹配结果。因此，只要输入数组未处理完毕，我们都需要保留所有遇到的正整数以备不时之需。如果存在特定的条件或者需求（例如内存限制或特定场景下的优化），可能会考虑在某些点清空pos数组，但这需要根据具体情况来定。