这个问题是leetcode中k空插槽的变体。 新的问题是,要求找到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
更新: 最后一天绽放的Kflowers = 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
更新: 最后一天开花 = 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