关于滑动窗口的算法



这个问题是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

相关内容

  • 没有找到相关文章

最新更新