难度: Hard
Submission
运行时间: 174 ms
内存: 18.2 MB
class Solution:
def kEmptySlots(self, bulbs: List[int], k: int) -> int:
n = len(bulbs)
days = [0] * n
for day, pos in enumerate(bulbs, 1):
days[pos-1] = day
ans = float("inf")
l, r = 0, k+1
while r < len(days):
for i in range(l+1, r):
if days[i] < days[l] or days[i] < days[r]:
l, r = i, i + k + 1
break
else:
ans = min(max(days[l], days[r]), ans)
l, r = r, r + k + 1
return ans if ans < float("inf") else -1
Explain
该题解的思路如下：首先初始化一个长度为 n 的数组 days，其中 days[i] 表示第 i+1 个灯泡在第几天被打开。然后遍历给定的 bulbs 数组，将每个灯泡被打开的日期记录在 days 数组中。接下来，使用双指针 l 和 r，初始时 l=0，r=k+1。在 l 和 r 之间查找是否存在比 days[l] 和 days[r] 小的值，如果存在，则将 l 移动到该位置，r 移动到 l+k+1。如果 l 和 r 之间的所有值都大于等于 days[l] 和 days[r]，则更新答案为 days[l] 和 days[r] 的较大值与当前答案的较小值。最后，如果找到满足条件的答案，则返回答案，否则返回 -1。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def kEmptySlots(self, bulbs: List[int], k: int) -> int:
n = len(bulbs)
days = [0] * n # 初始化 days 数组，记录每个灯泡被打开的日期
for day, pos in enumerate(bulbs, 1):
days[pos-1] = day # 记录第 pos 个灯泡在第 day 天被打开
ans = float("inf") # 初始化答案为正无穷大
l, r = 0, k+1 # 初始化双指针 l 和 r
while r < len(days):
for i in range(l+1, r):
if days[i] < days[l] or days[i] < days[r]: # 如果 l 和 r 之间存在比 days[l] 和 days[r] 小的值
l, r = i, i + k + 1 # 将 l 移动到该位置，r 移动到 l+k+1
break
else: # 如果 l 和 r 之间的所有值都大于等于 days[l] 和 days[r]
ans = min(max(days[l], days[r]), ans) # 更新答案为 days[l] 和 days[r] 的较大值与当前答案的较小值
l, r = r, r + k + 1 # 将 l 移动到 r，r 移动到 r+k+1
return ans if ans < float("inf") else -1 # 如果找到满足条件的答案，则返回答案，否则返回 -1
Explore
这样的检查确保了在灯泡l和灯泡r之间的确存在恰好k个未被打开的灯泡。如果l和r之间的任一灯泡比days[l]或days[r]更早打开，则这些灯泡不能算作是未打开的间隙中的一部分。从逻辑上说，我们在寻找连续的k个未打开的灯泡，其中两端的灯泡比这中间的任何一个灯泡更早被打开。这保证了找到的是正确的答案，而不是包含已打开灯泡的无效间隙。
当在l和r之间发现有比days[l]或days[r]更早打开的灯泡时，这意味着从当前l到r的范围内不能形成有效的k个未打开的间隙。将l移动到这个更早打开的灯泡位置是为了重新开始寻找可能的有效间隙，因为当前的间隙已被打破。重新设置l和r可以帮助我们重新评估新的潜在间隙，从而更有效地寻找到满足条件的灯泡组合。
如果l和r之间的所有灯泡都在days[l]和days[r]之后打开，这意味着从l到r之间确实存在恰好k个连续的灯泡尚未打开，且两端的灯泡先于中间的任何灯泡打开。这符合题目要求的条件，即找到两个相邻的灯泡，它们之间恰好有k个未打开的灯泡，并且这两个灯泡是第一个和最后一个被打开的。因此，这确实是一个有效的答案。
使用一个初始化为正无穷大的'ans'变量可以帮助我们在多个可能的答案中找到最小的天数。初始化为无穷大是为了确保任何有效的发现都会被捕捉到，因为任何实际的天数值都会小于无穷大。这种方法提供了一种简单而有效的方式来更新并比较寻找到的每个有效答案的最小值。