Hard
题目描述
给你两个从 1 开始索引的整数数组 nums 和 changeIndices，长度分别为 n 和 m。
最初，nums 中的所有索引都是未标记的。你的任务是标记 nums 中的所有索引。
在从 1 到 m（包括两端）的每一秒 s 中，你可以按顺序执行以下操作之一：
- 选择范围
[1, n]内的索引i，并将nums[i]减 1。 - 将
nums[changeIndices[s]]设为任何非负值。 - 选择范围
[1, n]内的索引i，其中nums[i]等于 0，并标记索引i。 - 什么都不做。
返回一个整数，表示在范围 [1, m] 内能够通过最优选择操作标记所有索引的最早秒数，如果不可能则返回 -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
示例 3：
输入：nums = [1,2,3], changeIndices = [1,2,3]
输出：-1
约束条件：
1 <= n == nums.length <= 50000 <= nums[i] <= 10^91 <= m == changeIndices.length <= 50001 <= changeIndices[i] <= n
解题思路
这是一道复杂的二分搜索加贪心算法题目。核心思路如下：
问题分析：
要标记所有索引，我们需要先将对应的 nums[i] 减到 0，然后再标记。总的时间需求是 sum(nums) + n（减值操作 + 标记操作）。
关键优化：
使用"设置操作"可以直接将 nums[changeIndices[s]] 设为 0，这样可以节省大量减值操作时间。设置操作的最优策略是：
- 只在值大于 0 的位置使用设置操作
- 设置操作应该在该索引第一次出现时使用
- 设置后需要在后续时间点标记该索引
算法步骤：
- 二分搜索：在
[1, m]范围内二分搜索最早能完成的时间点 - 贪心验证：对于每个候选时间
t，验证是否能在时间t内完成所有标记 - 优化选择：使用优先队列贪心地选择最优的设置操作，最大化节省的时间
验证函数：
- 从后往前遍历时间点，对每个可能的设置操作进行评估
- 使用最小堆维护当前选择的设置操作
- 确保每个设置操作后都有足够的时间进行标记
- 计算总的时间节省，判断是否满足时间限制
这种方法结合了二分搜索的效率和贪心算法的最优性，能够在合理时间内找到最优解。
代码实现
class Solution {
public:
int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
int n = nums.size(), m = changeIndices.size();
long long totalSum = 0;
for (int x : nums) totalSum += x;
auto check = [&](int t) -> bool {
vector<int> lastPos(n + 1, -1);
for (int i = 0; i < t; i++) {
lastPos[changeIndices[i]] = i;
}
vector<bool> canSet(n + 1, false);
for (int i = 1; i <= n; i++) {
if (lastPos[i] != -1 && nums[i - 1] > 0) {
canSet[i] = true;
}
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
long long saved = 0;
int operations = 0;
for (int i = t - 1; i >= 0; i--) {
int idx = changeIndices[i];
if (canSet[idx] && lastPos[idx] == i) {
pq.push({nums[idx - 1], idx});
}
if (!pq.empty()) {
auto [val, pos] = pq.top();
pq.pop();
saved += val - 1;
operations++;
}
}
long long needed = totalSum + n - saved;
return needed <= (long long)t - operations;
};
int left = 1, right = m, ans = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (check(mid)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
};
class Solution:
def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:
import heapq
n, m = len(nums), len(changeIndices)
total_sum = sum(nums)
def check(t):
last_pos = [-1] * (n + 1)
for i in range(t):
last_pos[changeIndices[i]] = i
can_set = [False] * (n + 1)
for i in range(1, n + 1):
if last_pos[i] != -1 and nums[i - 1] > 0:
can_set[i] = True
pq = []
saved = 0
operations = 0
for i in range(t - 1, -1, -1):
idx = changeIndices[i]
if can_set[idx] and last_pos[idx] == i:
heapq.heappush(pq, nums[idx - 1])
if pq:
val = heapq.heappop(pq)
saved += val - 1
operations += 1
needed = total_sum + n - saved
return needed <= t - operations
left, right = 1, m
ans = -1
while left <= right:
mid = (left + right) // 2
if check(mid):
ans = mid
right = mid - 1
else:
left = mid + 1
return ans
public class Solution {
public int EarliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
int n = nums.Length, m = changeIndices.Length;
long totalSum = nums.Sum(x => (long)x);
bool Check(int t) {
var lastPos = new int[n + 1];
Array.Fill(lastPos, -1);
for (int i = 0; i < t; i++) {
lastPos[changeIndices[i]] = i;
}
var canSet = new bool[n + 1];
for (int i = 1; i <= n; i++) {
if (lastPos[i] != -1 && nums[i - 1] > 0) {
canSet[i] = true;
}
}
var pq = new PriorityQueue<int, int>();
long saved = 0;
int operations = 0;
for (int i = t - 1; i >= 0; i--) {
int idx = changeIndices[i];
if (canSet[idx] && lastPos[idx] == i) {
pq.Enqueue(nums[idx - 1], nums[idx - 1]);
}
if (pq.Count > 0) {
int val = pq.Dequeue();
saved += val - 1;
operations++;
}
}
long needed = totalSum + n - saved;
return needed <= (long)t - operations;
}
int left = 1, right = m, ans = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (Check(mid)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}
var earliestSecondToMarkIndices = function(nums, changeIndices) {
const n = nums.length;
const m = changeIndices.length;
function canMarkAll(maxTime) {
const lastOccurrence = new Array(n + 1).fill(-1);
for (let i = 0; i < maxTime; i++) {
lastOccurrence[changeIndices[i]] = i;
}
for (let i = 1; i <= n; i++) {
if (lastOccurrence[i] === -1) return false;
}
const events = [];
for (let i = 1; i <= n; i++) {
events.push([lastOccurrence[i], i]);
}
events.sort((a, b) => a[0] - b[0]);
let usedSeconds = 0;
let availableSeconds = 0;
for (let i = 0; i < n; i++) {
const [time, idx] = events[i];
availableSeconds += time - usedSeconds;
usedSeconds = time + 1;
const needed = nums[idx - 1];
if (availableSeconds < needed) return false;
availableSeconds -= needed;
}
return true;
}
let left = 1, right = m;
let result = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (canMarkAll(mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
};
复杂度分析
| 复杂度类型 | 复杂度 |
|---|---|
| 时间复杂度 | O(m * m * log m) |
| 空间复杂度 | O(n + m) |
说明：
- 二分搜索需要 O(log m) 次迭代
- 每次验证函数需要 O(m * log m) 时间（主要是优先队列操作）
- 空间复杂度主要用于存储位置信息和优先队列