这个问题是leetcode中k empty slot的变体。
新的问题是,要求找出最后一天有k个连续开花的花。
例如
共7天,1代表开花,0代表未开花,K=3
day1:1 0 0 0 0 0 0
day2:1 0 1 0 0 0 0
day3:1 1 1 0 0 0 0 1st time find k consecutive bloomed flowers
更新:
LastDayBloomkFlowers=3个
day4:1 1 1 0 1 0 0
day5:1 1 1 0 1 1 0
day6:1 1 1 0 1 1 1 2nd time find k consecutive boomed flowers
更新:
LastDayBloomkFlowers=6个
day7:1 1 1 1 1 1 1
最后,花儿将在任何位置绽放
所以最终的解决方案是
lastDayBloomKflowers = 6
我们怎样才能得到
lastDayBloomKflowers
?时间复杂度
O(nlogn)
,空间O(n)
我知道如何解决最初的leetcode问题,我想使用树集,但对于这个变体,我不知道应该使用什么样的数据结构,并有效地解决它。
谢谢你抽出时间!
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
我正在寻求帮助的k空槽问题的变种。
由于leetcode上k空时隙问题的url是质数,你们中的一些人可能无法打开,我将在这里向你们展示原始k空时隙问题:
有一个有N个槽的花园。每一个槽里都有一朵花。N朵花将在N天内一朵朵绽放每天都会有一朵花盛开,从那时起它就处于盛开状态。
给定一个数组,花的数目从1到n。数组中的每个数字表示花在那天开放的地方。
例如,flowers[i]=x意味着在i日开花的唯一花将位于x位置,其中i和x将在1到n的范围内。
此外,给定一个整数K,你需要输出哪一天在开花的状态下存在两朵花,并且它们之间的花的数量是K并且这些花不开花。
最佳答案
让我们将日线转换为表示每天更新的位置的数组:
day1:1 0 0 0 0 0 0
array: [None,1] means on day 1, flower 1 bloomed
day2:1 0 1 0 0 0 0
array: [None,1,3] means on day 2, flower 3 bloomed
day3:1 1 1 0 0 0 0
array: [None,1,3,2] means on day 3 flower 2 bloomed
day4:1 1 1 0 1 0 0
array: [None,1,3,2,5]
day5:1 1 1 0 1 1 0
array: [None,1,3,2,5,6]
day6:1 1 1 0 1 1 1
array: [None,1,3,2,5,6,7]
day7:1 1 1 1 1 1 1
array: [None,1,3,2,5,6,7,4]
现在让我们使用滑动窗口迭代这个数组:
[None,1,3,2,5,6,7,4]
k: 1 |-| min,max 1
k: 2 |---| min,max 1,3
k: 3 |-----| min,max 1,3 and count is 3 so days must be consecutive,
record (1,3) and day 3
k: 3 |-----| min,max 2,5 not consecutive
k: 3 |-----| min,max 2,6 not consecutive
k: 3 |-----| min,max 5,7 and count is 3 so days must be consecutive
also 6 is greater than 3 and (5,7) does not
overlap with (1,3) so the last day is now
known to be 6
k: 3 |-----| min,max 4,7 not consecutive