Codility FrogRiverOne解法逻辑疑问：布尔数组与索引减1原理

我来帮你拆解这个解法的每一步逻辑，搞清楚为什么要这么做。

为什么要创建covered_a标记数组？ #

我们的核心目标是跟踪1到X的每个位置是否已经被树叶覆盖，而且只需要关注每个位置第一次被覆盖的时刻——毕竟我们要找的是所有位置都凑齐的最早时间。

covered_a数组的长度正好是X，对应我们需要覆盖的1到X这X个位置。初始值全设为-1，代表这个位置还没有树叶落下。当某个位置第一次被树叶覆盖时，我们就把这个位置对应的数组元素从-1改成实际的位置值（其实改成任意非-1的值都可以，这里只是做个“已覆盖”的标记），同时把covered计数器加1。这个计数器的作用很关键：它用来统计已经被覆盖的不同位置的数量，一旦它等于X，就说明所有1到X的位置都有树叶了，此时的时间（也就是当前遍历到的index）就是我们要找的最早过河时间。

为什么要对A的元素逐个减1？ #

这是因为数组的索引是从0开始的，但我们的树叶位置是从1到X。比如位置1对应数组的第0个索引，位置X对应数组的第X-1个索引。举个例子，当X=5时，我们需要跟踪位置1、2、3、4、5，对应的covered_a数组索引就是0、1、2、3、4。所以当我们拿到A中的元素（比如A[6]=5），减去1之后得到4，正好对应covered_a的第4个位置，这样就能准确找到对应的标记位，判断这个位置是否已经被覆盖过。说白了就是把“位置编号”转换成“数组索引”，让我们能正确操作标记数组。

跟着示例走一遍，更直观 #

拿题目里的例子：X=5，A=[1,3,1,4,2,3,5,4]

• 初始状态：covered=0，covered_a=[-1,-1,-1,-1,-1]
• 第0秒（index=0），元素是1：减1得0，covered_a[0]是-1，所以标记为1，covered变成1。此时还没到5，继续。
• 第1秒（index=1），元素是3：减1得2，covered_a[2]是-1，标记为3，covered变成2。继续。
• 第2秒（index=2），元素是1：减1得0，covered_a[0]已经不是-1了，说明这个位置已经有树叶了，跳过，covered不变。
• 第3秒（index=3），元素是4：减1得3，covered_a[3]是-1，标记为4，covered变成3。继续。
• 第4秒（index=4），元素是2：减1得1，covered_a[1]是-1，标记为2，covered变成4。继续。
• 第5秒（index=5），元素是3：减1得2，covered_a[2]已经被标记过了，跳过，covered不变。
• 第6秒（index=6），元素是5：减1得4，covered_a[4]是-1，标记为5，covered变成5，等于X=5，所以返回当前index=6，这就是正确答案。

再看另一个测试用例：X=2，A=[2,2,2,2,2]

• 初始covered=0，covered_a=[-1,-1]
• 第0秒，元素2：减1得1，covered_a[1]是-1，标记为2，covered变成1。
• 后面所有元素都是2，减1后都是1，covered_a[1]已经不是-1了，所以covered一直是1，永远到不了2。循环结束后返回-1，符合预期。

总结一下这个解法的思路 #

这个解法用了非常高效的策略：

• 时间复杂度是O(N)，因为每个元素只遍历一次；
• 空间复杂度是O(X)，用来存储标记数组；
• 计数器covered让我们不用每次都检查整个数组是否全被覆盖，只要计数器达到X就立即返回，保证了我们能拿到最早的时间点。

内容的提问来源于stack exchange，提问作者Vaebhav