这个问题是leetcode上“k空插槽”的一个变种。
新的问题是,找到最后一天有k朵连续开放的花。
例如,总共7天,1代表花开放,0代表花未开放,k=3。
更新:
更新:
由于LeetCode上k个空槽问题的网址是针对质数的,因此你们中的一些人可能无法打开,所以我将在这里展示原始的k个空槽问题:
有一个花园,里面有N个插槽。在每个插槽中都有一朵花。这N朵花将在N天内依次开放。每天只会有一朵花开放,并且它从那时起就处于盛开状态。
给定一个数组flowers,其中包含1到N的数字。数组中的每个数字表示花在当天开放的位置。
例如,flowers[i] = x表示第i天开放的唯一花朵将位于位置x,其中i和x的范围将从1到N。
还给定一个整数k,你需要输出存在两朵盛开的花,它们之间有k朵未开放的花,并且它们不是盛开状态的那一天。
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个空槽问题的网址是针对质数的,因此你们中的一些人可能无法打开,所以我将在这里展示原始的k个空槽问题:
有一个花园,里面有N个插槽。在每个插槽中都有一朵花。这N朵花将在N天内依次开放。每天只会有一朵花开放,并且它从那时起就处于盛开状态。
给定一个数组flowers,其中包含1到N的数字。数组中的每个数字表示花在当天开放的位置。
例如,flowers[i] = x表示第i天开放的唯一花朵将位于位置x,其中i和x的范围将从1到N。
还给定一个整数k,你需要输出存在两朵盛开的花,它们之间有k朵未开放的花,并且它们不是盛开状态的那一天。