标记所有下标的最早秒数 II
难度:
标签:
题目描述
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
iin the range[1, n]and decrementnums[i]by1. - Set
nums[changeIndices[s]]to any non-negative value. - Choose an index
iin the range[1, n], wherenums[i]is equal to0, and mark indexi. - 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 = [3,2,3], changeIndices = [1,3,2,2,2,2,3] Output: 6 Explanation: In this example, we have 7 seconds. The following operations can be performed to mark all indices: Second 1: Set nums[changeIndices[1]] to 0. nums becomes [0,2,3]. Second 2: Set nums[changeIndices[2]] to 0. nums becomes [0,2,0]. Second 3: Set nums[changeIndices[3]] to 0. nums becomes [0,0,0]. Second 4: Mark index 1, since nums[1] is equal to 0. Second 5: Mark index 2, since nums[2] is equal to 0. Second 6: Mark index 3, since nums[3] 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 2:
Input: nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2] Output: 7 Explanation: In this example, we have 8 seconds. The following operations can be performed to mark all indices: Second 1: Mark index 1, since nums[1] is equal to 0. Second 2: Mark index 2, since nums[2] is equal to 0. Second 3: Decrement index 4 by one. nums becomes [0,0,1,1]. Second 4: Decrement index 4 by one. nums becomes [0,0,1,0]. Second 5: Decrement index 3 by one. nums becomes [0,0,0,0]. Second 6: Mark index 3, since nums[3] is equal to 0. Second 7: Mark index 4, since nums[4] 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 7th second. Hence, the answer is 7.
Example 3:
Input: nums = [1,2,3], changeIndices = [1,2,3] Output: -1 Explanation: In this example, it can be shown that it is impossible to mark all indices, as we don't have enough seconds. Hence, the answer is -1.
Constraints:
1 <= n == nums.length <= 50000 <= nums[i] <= 1091 <= m == changeIndices.length <= 50001 <= changeIndices[i] <= n
代码结果
运行时间: 29 ms, 内存: 17.2 MB
/*
* 思路：
* 1. 使用 Java Stream API 在每一秒内对 nums 的对应元素变为 0。
* 2. 每次变更后检查 nums，如果有 0 的位置则标记。
* 3. 重复上述操作直到所有位置都标记或时间用完。
*/
import java.util.stream.IntStream;
public class Solution {
public int earliestTimeToMarkAll(int[] nums, int[] changeIndices) {
int n = nums.length;
int m = changeIndices.length;
boolean[] marked = new boolean[n];
int markedCount = 0;
for (int s = 0; s < m; s++) {
int index = changeIndices[s] - 1;
nums[index] = 0;
// Check and mark indices
markedCount += (int) IntStream.range(0, n)
.filter(i -> nums[i] == 0 && !marked[i])
.peek(i -> marked[i] = true)
.count();
// Check if all are marked
if (markedCount == n) {
return s + 1;
}
}
return -1;
}
}解释
方法:
此题解通过模拟操作过程来确定标记所有下标的最早秒数。初始时，定义几个变量：rsum为总操作次数，ctx为必需操作次数，idxn为可能减少操作次数的下标集合。遍历nums计算总操作次数和必需操作次数。接着遍历changeIndices数组，对于每个元素，减少总操作次数，并调整必需操作次数和可能减少操作次数的下标集合。最后，根据剩余的总操作次数和必需操作次数来判断并返回最早标记所有下标的秒数。如果操作无法完成，则返回-1。
时间复杂度:
O(n + m)
空间复杂度:
O(n)
代码细节讲解
🦆
在题解中使用的变量`rsum`、`ctx`、`rs`、`idxn`各代表什么具体含义？题解中对这些变量的解释是否充分？
▷🦆
题解中提到`如果x < 2，则ctx += x + 1`，这里为什么要将x小于2的情况特别处理，对算法的正确性和效率有何影响？
▷🦆
在遍历`changeIndices`数组时，逻辑`if x in idxn`后对`rsum`和`ctx`的调整是如何影响算法决策的？
▷