Leetcode 683. K 个空花盆 （滑动窗口 或者 线段树）
花园里有 N 个花盆，每个花盆里都有一朵花。这 N 朵花会在 N 天内依次开放，每天有且仅有一朵花会开放并且会一直盛开下去。
给定一个数组 flowers 包含从 1 到 N 的数字，每个数字表示在那一天开放的花所在的花盆编号。
例如， flowers[i] = x 表示在第 i 天盛开的花在第 x 个花盆中，i 和 x 都在 1 到 N 的范围内。
给你一个整数 k，请你输出在哪一天恰好有两朵盛开的花，他们中间间隔了 k 朵花并且都没有开放。
如果不存在，输出 -1。
样例 1:
输入:
flowers: [1,3,2]
k: 1
输出: 2
解释: 在第二天，第一朵和第三朵花都盛开了。
样例 2:
输入:
flowers: [1,2,3]
k: 1
输出: -1
注释 :
给定的数组范围是 [1, 20000]。
用DAYS数组保存第i个花盆开花的时间。保持left花盆和right花盆中间有k个花盆，
如果left和right之间的每一个花盆的开花时间都大于left花盆的开花时间同时大于right 花盆的开花时间，则这个left right花盆pair是满足条件的。 其中较晚开花的那个花盆的时间即为一个满足条件的答案。总体上我们应该返回满足这个条件的一个最小的解。
由于我们需要一个最小的解，所以对于满足条件时，我们可以直接更新left=right，right=left+K+1。 因为就算之前left~right之间的有满足条件的区间，但是其结果一定会比当前的结果大。
如果left 和 right之间有一个花盆i 其开花时间小于二者任意一个，说明left 和right不可能满足，同时left~i之间的花盆开花的时间都大于left，right花盆，所以都不能是下一步left的开始，（因为中间必定还是包含这个当前的i，所以会不满足条件。） 于是可以直接更新left=i，right=left+K+1
整个滑动窗口只会在n个数上滑动一次，所以时间复杂度是O(N)
代码class Solution:
def kEmptySlots(self, bulbs: List[int], K: int) -> int:
days=[0]*(len(bulbs)+1) # 第i个花盆开花的时间
for i,b_num in enumerate(bulbs):
cur_day=i+1
days[b_num]=cur_day
result=-1
left=1
right=left+K+1
# print(days)
while rightdays[left] and days[i]>days[right]:
continue
else:
flag=False
left=i
right=left+K+1
break
if flag:
cur_result=max(days[left],days[right])
result=min(result,cur_result) if result!=-1 else cur_result
left=right
right=left+K+1
return result
解题思路2 （线段树）
思路为线段树，记录N个花盆的开花情况，然后统计区间里开花的花盆数
对于第i天开花的b_num号花盆，则将区间b_num~b_num和置位1，如果满足以下两个条件中的一个，则可以返回当前的i作为结果：
1.区间b_num-K ~ b_num和为1，且区间 b_num-K-1 ~ b_num的和为2 （满足条件，且之前开的花在左边）
2.区间b_num ~ b_num+K 和为1，且区间b_num ~ b_num+k+1 和为2 （满足条件，且之前开的花在有右边）
如果遍历了所有天都不满足情况，则返回-1
由于更新线段树和区间查询的时间复杂度都是O(log(n)) 所以总体时间复杂度是O(nlog(n))
class Solution:
def kEmptySlots(self, bulbs: List[int], K: int) -> int:
N=len(bulbs)
self.tree=[[0,0,0] for i in range(N*4)] # [0,0,0]表示一个tree node，三个数分别表示区间左边l 区间右边r 以及区间l~r的和， 初始化为全0
self.build_tree(1,N,0) # 构建线段树
for i,b_num in enumerate(bulbs):
cur_day=i+1
self.update_tree(b_num,0)
left=b_num-K-1
right=b_num+K+1
if left>=1: # 先判断左边的K的花盆
if self.query_tree(left+1,b_num,0)==1 and self.query_tree(left,b_num,0)==2 :
return cur_day
if right<=N:
if self.query_tree(b_num,right-1,0)==1 and self.query_tree(b_num,right,0)==2:
return cur_day
return -1
def build_tree(self,l,r,i): #i从0开始，左右子树下标分别是2i+1 和 2i+2
if l==r:
self.tree[i][0]=l
self.tree[i][1]=r
self.tree[i][2]=0
return
mid=(l+r)//2
self.build_tree(l,mid,i*2+1)
self.build_tree(mid+1,r,i*2+2)
self.tree[i][2]=self.tree[i*2+1][2]+self.tree[i*2+2][2]
self.tree[i][0]=l
self.tree[i][1]=r
return
def update_tree(self,index,i):
l,r,v=self.tree[i]
if l==r:
self.tree[i][2]+=1
return
mid=(l+r)//2
if index=mid+1:
return self.query_tree(left,right,i*2+2)
if right<=mid:
return self.query_tree(left,right,i*2+1)
cur_sum=0
cur_sum+=self.query_tree(left,mid,i*2+1)
cur_sum+=self.query_tree(mid+1,right,i*2+2)
return cur_sum
作者：木子-勇士心
