标记所有下标的最早秒数 I

难度: Medium

给你两个下标从 1 开始的整数数组 nums 和 changeIndices ，数组的长度分别为 n 和 m 。

一开始，nums 中所有下标都是未标记的，你的任务是标记 nums 中所有下标。

从第 1 秒到第 m 秒（包括第 m 秒），对于每一秒 s ，你可以执行以下操作之一：

选择范围 [1, n] 中的一个下标 i ，并且将 nums[i] 减少 1 。
如果 nums[changeIndices[s]] 等于 0 ，标记下标 changeIndices[s] 。
什么也不做。

请你返回范围 [1, m] 中的一个整数，表示最优操作下，标记 nums 中所有下标的 最早秒数 ，如果无法标记所有下标，返回 -1 。

示例 1：

输入：nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1]
输出：8
解释：这个例子中，我们总共有 8 秒。按照以下操作标记所有下标：
第 1 秒：选择下标 1 ，将 nums[1] 减少 1 。nums 变为 [1,2,0] 。
第 2 秒：选择下标 1 ，将 nums[1] 减少 1 。nums 变为 [0,2,0] 。
第 3 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [0,1,0] 。
第 4 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [0,0,0] 。
第 5 秒，标记 changeIndices[5] ，也就是标记下标 3 ，因为 nums[3] 等于 0 。
第 6 秒，标记 changeIndices[6] ，也就是标记下标 2 ，因为 nums[2] 等于 0 。
第 7 秒，什么也不做。
第 8 秒，标记 changeIndices[8] ，也就是标记下标 1 ，因为 nums[1] 等于 0 。
现在所有下标已被标记。
最早可以在第 8 秒标记所有下标。
所以答案是 8 。

示例 2：

输入：nums = [1,3], changeIndices = [1,1,1,2,1,1,1]
输出：6
解释：这个例子中，我们总共有 7 秒。按照以下操作标记所有下标：
第 1 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [1,2] 。
第 2 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [1,1] 。
第 3 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [1,0] 。
第 4 秒：标记 changeIndices[4] ，也就是标记下标 2 ，因为 nums[2] 等于 0 。
第 5 秒：选择下标 1 ，将 nums[1] 减少 1 。nums 变为 [0,0] 。
第 6 秒：标记 changeIndices[6] ，也就是标记下标 1 ，因为 nums[1] 等于 0 。
现在所有下标已被标记。
最早可以在第 6 秒标记所有下标。
所以答案是 6 。

示例 3：

Input: nums = [0,1], changeIndices = [2,2,2]
Output: -1
Explanation: 这个例子中，无法标记所有下标，因为下标 1 不在 changeIndices 中。
所以答案是 -1 。

提示：

1 <= n == nums.length <= 2000
0 <= nums[i] <= 10⁹
1 <= m == changeIndices.length <= 2000
1 <= changeIndices[i] <= n

Submission

运行时间: 38 ms

内存: 16.5 MB

class Solution:
    def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:
        n, m = len(nums), len(changeIndices)
        t = n + sum(nums)
        if t > m:
            return -1
        d = {}
        for i, ni in enumerate(changeIndices, 1):
            d[ni] = i
            if i >= t and len(d) >= n:
                break
        else:
            return -1
        
        def f(d):
            s = 0
            for i, ni in sorted((i, ni) for ni, i in enumerate(d)):
                s += nums[ni] + 1
                if s > i:
                    return
            return True
            
        d = [d.pop(i) for i in range(1, n + 1)]
        if f(d):
            return i
        a, b = i + 1, m + 1
        while a < b:
            c = a + b >> 1
            d1 = d.copy()
            for i in range(a - 1, c):
                d1[changeIndices[i] - 1] = i + 1
            if f(d1):
                b = c
                continue
            a, d = c + 1, d1
        return a if a <= m else -1

Explain

题解的核心思路是通过模拟和二分查找来确定最早的秒数，其中所有的 `nums` 下标都被标记。首先，计算理论上需要的最小操作次数 `t`，这包括将每个元素减到0需要的次数加上每个元素至少需要被标记一次。如果总的时间段 `m` 小于 `t`，则直接返回 `-1`。接着使用一个字典 `d` 来记录每个下标最后一次出现在 `changeIndices` 中的时间。利用这个字典，可以通过一个辅助函数 `f` 来检查在当前时间是否所有的 `nums` 元素都可以被归零并且被标记。最后，使用二分查找方法来找到最早的可能秒数，使得所有下标都被成功标记。

时间复杂度: O(m log m + n log n)

空间复杂度: O(n)

class Solution:
    def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:
        n, m = len(nums), len(changeIndices)
        # 计算理论上需要的最小操作次数
        t = n + sum(nums)
        if t > m: # 检查是否有足够的秒数
            return -1
        d = {}
        for i, ni in enumerate(changeIndices, 1):
            d[ni] = i # 记录每个下标最后出现的时间
            if i >= t and len(d) >= n: # 如果已经足够标记所有下标
                break
        else:
            return -1
        
        def f(d): # 辅助函数，检查是否所有的 nums 元素都可以在指定时间内归零并且被标记
            s = 0
            for i, ni in sorted((i, ni) for ni, i in enumerate(d)):
                s += nums[ni] + 1
                if s > i:
                    return
            return True
        
        d = [d.pop(i) for i in range(1, n + 1)]
        if f(d):
            return i
        a, b = i + 1, m + 1
        while a < b: # 二分查找最早可能的秒数
            c = a + b >> 1
            d1 = d.copy()
            for i in range(a - 1, c):
                d1[changeIndices[i] - 1] = i + 1
            if f(d1):
                b = c # 如果可以标记所有下标，更新上界
                continue
            a, d = c + 1, d1 # 更新下界
        return a if a <= m else -1

Explore

在二分查找的循环中，复制并更新字典`d1`是用于测试某个时间点（秒数）是否能满足所有`nums`下标都被标记的条件。因为二分查找试图找到最小的可能时间，所以每次循环都需要基于当前的中间点修改字典来反映哪些下标在这个时间点之前被标记。复制字典是为了保留原始状态，这样在下一轮二分查找时可以从未修改的状态开始。这种方法的潜在效率问题包括：1) 每次循环都进行字典复制，这在字典较大时可能非常耗时；2) 更新字典和检查条件的过程可能每次都需要遍历整个字典，造成较高的计算复杂度。

如果`m`恰好等于`t`，算法并不总是能成功标记所有下标。理论最小操作次数`t`只是一个初步的估计，它假设每个元素恰好在它需要被归零的时间被标记。实际情况中，元素的标记可能不是均匀分布的，特别是如果`changeIndices`中的下标不是均匀涵盖所有`nums`的下标，或者标记的顺序与减少元素的需求不匹配时，即便`m`等于`t`也可能无法在所有的下标都恰好在需要的时刻被标记。