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

You are given two 1-indexed integer arrays, nums and, changeIndices, having lengths n and m, respectively.

Initially, all indices in nums are unmarked. Your task is to mark all indices in nums.

In each second, s, in order from 1 to m (inclusive), you can perform one of the following operations:

• Choose an index i in the range [1, n] and decrement nums[i] by 1.
• If nums[changeIndices[s]] is equal to 0, mark the index changeIndices[s].
• Do nothing.

Return an integer denoting the earliest second in the range [1, m] when all indices in nums can be marked by choosing operations optimally, or -1 if it is impossible.

 

Example 1:

Input: nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1]
Output: 8
Explanation: In this example, we have 8 seconds. The following operations can be performed to mark all indices:
Second 1: Choose index 1 and decrement nums[1] by one. nums becomes [1,2,0].
Second 2: Choose index 1 and decrement nums[1] by one. nums becomes [0,2,0].
Second 3: Choose index 2 and decrement nums[2] by one. nums becomes [0,1,0].
Second 4: Choose index 2 and decrement nums[2] by one. nums becomes [0,0,0].
Second 5: Mark the index changeIndices[5], which is marking index 3, since nums[3] is equal to 0.
Second 6: Mark the index changeIndices[6], which is marking index 2, since nums[2] is equal to 0.
Second 7: Do nothing.
Second 8: Mark the index changeIndices[8], which is marking index 1, since nums[1] is equal to 0.
Now all indices have been marked.
It can be shown that it is not possible to mark all indices earlier than the 8th second.
Hence, the answer is 8.

Example 2:

Input: nums = [1,3], changeIndices = [1,1,1,2,1,1,1]
Output: 6
Explanation: In this example, we have 7 seconds. The following operations can be performed to mark all indices:
Second 1: Choose index 2 and decrement nums[2] by one. nums becomes [1,2].
Second 2: Choose index 2 and decrement nums[2] by one. nums becomes [1,1].
Second 3: Choose index 2 and decrement nums[2] by one. nums becomes [1,0].
Second 4: Mark the index changeIndices[4], which is marking index 2, since nums[2] is equal to 0.
Second 5: Choose index 1 and decrement nums[1] by one. nums becomes [0,0].
Second 6: Mark the index changeIndices[6], which is marking index 1, since nums[1] is equal to 0.
Now all indices have been marked.
It can be shown that it is not possible to mark all indices earlier than the 6th second.
Hence, the answer is 6.

Example 3:

Input: nums = [0,1], changeIndices = [2,2,2]
Output: -1
Explanation: In this example, it is impossible to mark all indices because index 1 isn't in changeIndices.
Hence, the answer is -1.

 

Constraints:

• 1 <= n == nums.length <= 2000
• 0 <= nums[i] <= 109
• 1 <= m == changeIndices.length <= 2000
• 1 <= changeIndices[i] <= n

/*
 * 思路：
 * 1. 使用流来遍历秒数并依次执行操作。
 * 2. 使用条件和操作符来处理 nums 中元素减少及标记对应下标。
 * 3. 利用流的过滤和计数功能检查是否所有下标都被标记。
 * 4. 返回标记所有下标的最早秒数，如果无法标记全部下标返回 -1。
 */

import java.util.stream.IntStream;

public class SolutionStream {
    public int markAllIndices(int[] nums, int[] changeIndices) {
        int n = nums.length;
        int m = changeIndices.length;
        boolean[] marked = new boolean[n];

        return IntStream.range(0, m)
            .filter(s -> {
                int index = changeIndices[s] - 1;
                if (nums[index] > 0) {
                    nums[index]--;
                }
                if (nums[index] == 0 && !marked[index]) {
                    marked[index] = true;
                }
                return IntStream.of(marked).allMatch(b -> b);
            })
            .findFirst()
            .orElse(-1) + 1;
    }
}

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

O(m log m + n log n)

O(n)