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

难度: Hard

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

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

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

选择范围 [1, n] 中的一个下标 i ，并且将 nums[i] 减少 1 。
将 nums[changeIndices[s]] 设置成任意的非负整数。
选择范围 [1, n] 中的一个下标 i ，满足 nums[i] 等于 0, 并标记下标 i 。
什么也不做。

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

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1,2,3], changeIndices = [1,2,3]
输出：-1
解释：这个例子中，无法标记所有下标，因为我们没有足够的秒数。
所以答案是 -1 。

提示：

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

Submission

运行时间: 29 ms

内存: 17.2 MB

class Solution:
    def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:
        rsum,ctx,rs,idxn=0,0,0,set()
        lc=len(changeIndices)
        # rsum 为最多需要操作次数，ctx为不可避免操作次数。 idxn为可能缩减次数的下标集合
        for i,x in enumerate(nums):
            rsum+=x+1
            if x<2:
                ctx+=x+1
            else:
                idxn.add(i+1)
        
        for k,x in enumerate(changeIndices):
            rsum-=1
            if x in idxn:
                idxn-={x}
                rsum-=nums[x-1]-1
                ctx+=1
            elif ctx:
                ctx-=1

            # ************* 后续为结束条件判断 *******************************
            
            if rsum==1:
                return -1 if (t:=k+1+max(ctx,1))>lc   else t
            if rsum<=0:
                if ctx==0: return k+1
                if rsum<0: return -1 if (t:=k+2)>lc   else t
                # 下面是不断尝试蒙出来的，本人没有找到依据。
                if idxn: ctx=min(ctx,len(idxn))
                return -1 if (t:=k+1+ctx)>lc   else t
        return -1

Explain

此题解通过模拟操作过程来确定标记所有下标的最早秒数。初始时，定义几个变量：rsum为总操作次数，ctx为必需操作次数，idxn为可能减少操作次数的下标集合。遍历nums计算总操作次数和必需操作次数。接着遍历changeIndices数组，对于每个元素，减少总操作次数，并调整必需操作次数和可能减少操作次数的下标集合。最后，根据剩余的总操作次数和必需操作次数来判断并返回最早标记所有下标的秒数。如果操作无法完成，则返回-1。

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

空间复杂度: O(n)

class Solution:
    def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:
        rsum, ctx, rs, idxn = 0, 0, 0, set()
        lc = len(changeIndices)
        # rsum 为最多需要操作次数，ctx为不可避免操作次数。 idxn为可能缩减次数的下标集合
        for i, x in enumerate(nums):
            rsum += x + 1
            if x < 2:
                ctx += x + 1
            else:
                idxn.add(i + 1)
        
        for k, x in enumerate(changeIndices):
            rsum -= 1
            if x in idxn:
                idxn -= {x}
                rsum -= nums[x - 1] - 1
                ctx += 1
            elif ctx:
                ctx -= 1
            # ************* 后续为结束条件判断 *******************************
            if rsum == 1:
                return -1 if (t := k + 1 + max(ctx, 1)) > lc else t
            if rsum <= 0:
                if ctx == 0: return k + 1
                if rsum < 0: return -1 if (t := k + 2) > lc else t
                # 下面是不断尝试蒙出来的，本人没有找到依据。
                if idxn: ctx = min(ctx, len(idxn))
                return -1 if (t := k + 1 + ctx) > lc else t
        return -1

Explore

`rsum`代表总操作次数，即对所有下标标记所需的最大操作次数。`ctx`代表必需操作次数，即不受`changeIndices`影响的下标所需的最小操作次数。`rs`似乎未在代码中使用，可能是冗余或错误。`idxn`是一个集合，包含那些可能通过`changeIndices`减少操作次数的下标。对于这些变量的解释，除了`rs`未被使用外，其他变量的功能已经在题解中有所解释，但解释不是特别详细，尤其是对于`idxn`的作用和重要性，可以进一步详细说明其如何影响操作次数的调整。

当`x < 2`时，意味着该位置的元素值较小（0或1），因此必须要进行`x + 1`次操作才能完成标记。这种情况特别处理是因为这些下标的操作次数不能通过`changeIndices`减少（因为即使减少也无法降至0以下），因此必须将它们的操作次数直接计入必需操作次数`ctx`。这样的处理确保算法在计算最早完成时间时能正确地优先考虑这些固定的操作次数，从而提高算法的正确性。此外，这也使得算法更加高效，因为它帮助避免在这些不能通过`changeIndices`优化的下标上浪费计算资源。

当`x`在`idxn`集合中时，表示`x-1`下标处的元素可以通过`changeIndices`减少操作次数。因此，代码中减少了`rsum`（总操作次数减1）和额外减去`nums[x-1] - 1`（因为已通过一次改变减少了，剩余的操作次数也相应减少）。同时，因为现在这个下标的操作次数已被优化，所以将其从`idxn`中移除，并将`ctx`（必需操作次数）增加1（即使操作次数减少，该次操作还是必须进行的）。这种调整帮助算法在每次改变时重新评估剩余的总操作次数和必需操作次数，从而动态决定最早的完成时刻或判断是否可能完成所有操作。