企业官网建设流程全解析

这是一道经典的结合了二分查找与反悔贪心算法的困难题。以下是详细的思路解析与 Java 代码实现。

核心思路分析

1. 二分查找答案：
题目要求找出标记所有下标的“最早秒数”。由于时间具有单调性（如果在 t 秒内能完成，那么在 t+1 秒内也一定能完成），我们可以对时间进行二分查找，将最优化问题转化为判定问题：判断在给定的 mid 秒内，是否能完成所有下标的标记。

2. 反悔贪心策略：
对于数组中的每个元素，将其变为 0 有两种方式：
- 方式一（直接置零）：利用 changeIndices 提供的机会，直接将 nums[i] 设置为 0。这消耗 1 秒，且必须在 nums[i] 对应的最早出现时机进行。
- 方式二（逐步递减）：每次将 nums[i] 减 1，直到变为 0。这需要消耗 nums[i] 秒，且可以在任意空闲时间进行。

无论采用哪种方式，元素变为 0 后，都需要额外消耗 1 秒来进行“标记”操作。因此，总耗时 = 所有元素的置零/递减耗时 + n（标记耗时）。

3. 倒序遍历与反悔机制：
在 check(lim) 函数中，我们从后往前遍历前 lim 秒的时间线：
- 如果当前秒不是某个下标 i 的首次出现，或者 nums[i] <= 1（直接置零不划算），我们将其视为空闲时间（可用时间 res++）。
- 如果是首次出现且 nums[i] > 1，我们优先尝试使用“方式一”（直接置零），此时消耗 1 秒，并将该元素放入小根堆中记录其代价。
- 反悔操作：如果当前可用时间 res == 0，说明时间不够了。此时我们需要比较当前元素的值与堆顶元素（之前选择直接置零的元素中代价最小的）。如果当前元素的值更大，说明之前对堆顶元素使用“方式一”是不划算的，我们应该“反悔”：撤销堆顶元素的直接置零（改为逐步递减，归还 1 秒并增加其递减代价），转而将当前元素直接置零。
- 最后，判断剩余的可用时间 res 是否大于等于剩余需要逐步递减的总和 s。

Java 代码实现

import java.util.PriorityQueue;

class Solution {
public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
int n = nums.length, m = changeIndices.length;

// 计算理论上的最小耗时：所有元素逐步递减的总和 + n个标记操作
long tot = 0;
for (int num : nums) tot += num;
tot += n;

// 预处理：记录每个下标在 changeIndices 中最早出现的位置
int[] first = new int[n];
for (int i = 0; i < n; i++) first[i] = -1;
for (int i = m - 1; i >= 0; i--) {
first[changeIndices[i] - 1] = i; // 转为0-indexed
}

// 二分查找最早秒数
int l = n, r = m + 1;
while (l < r) {
int mid = (l + r) >> 1;
if (check(nums, changeIndices, first, mid, tot)) {
r = mid;
} else {
l = mid + 1;
}
}

return r <= m ? r : -1;
}

private boolean check(int[] nums, int[] tag, int[] first, int lim, long tot) {
long res = 0; // 当前可用的空闲时间
long s = tot; // 还需要通过“逐步递减”或“直接置零”消耗的总代价
// 小根堆，用于反悔贪心，存储已经选择“直接置零”的元素的值
PriorityQueue<Integer> pq = new PriorityQueue<>();

// 倒序遍历前 lim 秒
for (int i = lim - 1; i >= 0; i--) {
int id = tag[i] - 1; // 转为0-indexed
int x = nums[id];

// 如果不是首次出现，或者值<=1，直接作为空闲时间
if (x <= 1 || i != first[id]) {
res++;
continue;
}

// 如果是首次出现且 x > 1，考虑是否进行“直接置零”操作
if (res == 0) {
// 如果没有空闲时间，尝试反悔
if (!pq.isEmpty() && x > pq.peek()) {
// 反悔：撤销堆顶元素的直接置零，改为逐步递减
s += pq.poll() + 1;
res += 2; // 归还1秒置零时间 + 1秒标记时间
} else {
// 无法反悔或当前元素不值得反悔，当前秒作为空闲时间
res++;
continue;
}
}

// 对当前元素执行“直接置零”操作
s -= (x + 1); // 扣除直接置零和标记的代价
pq.offer(x); // 记录到堆中，以便未来可能被反悔
res--; // 消耗1秒进行置零操作
}

// 判断剩余的空闲时间是否足以完成所有剩余的“逐步递减”操作
return res >= s;
}
}

复杂度分析
- 时间复杂度：O(m log m)。二分查找需要 O(log m) 次迭代，每次 check 函数内部倒序遍历并配合优先队列操作需要 O(m log m) 的时间。
- 空间复杂度：O(m)。主要用于存储 first 数组和优先队列。㇏