滑动窗口算法

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

更新:

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朵未开放的花,并且它们不是盛开状态的那一天。

请仔细格式化问题。 - user202729
我已经纠正了一些打字错误。 - Tianbo
我们无法访问问题链接,似乎只有高级用户才能访问,请您更新此帖并附上问题。谢谢。 - zenwraight
我很困惑。你在问题中添加了一个部分,“我将在此处显示原始问题: ”。这是您需要帮助解决的问题的描述,还是您已经知道如何解决的问题的描述? - גלעד ברקן
因为有一些评论说他们无法打开链接,因为链接是给Leetcode上的素数问题用的。我附上原始链接的原因是为了让描述更加清晰。我知道如何解决Leetcode上的原始问题,我是在寻求帮助我发布的变种问题。我看过你聪明的解决方案,但是我发现有些情况不正确,我已经列出了错误的情况。你能帮我修复吗?我非常感谢你的时间和努力。 - Tianbo
1个回答

0

让我们将日行转换为表示每天更新了哪个位置的数组:

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

是的,我明白了,你真是个天才!非常感谢。基于你的解决方案,我想到了一个在滑动窗口中查找最小值和最大值的优化方法,我可以使用两个双端队列来查找最小值和最大值,这样时间复杂度就是O(n)。 - Tianbo
我发现了一个 BUG! 第1天:1 0 0 0 0 0 0第2天:1 0 1 0 0 0 0第3天:1 1 1 0 0 0 0 寻找连续开花的第 k 朵花的首次出现时间 更新:lastDayBloomKflowers = 3第4天:1 1 1 1 0 0 0 在你的算法中,它会找到当 k=3 朵花开放时的最后一天是第 4 天,但是,第 4 天并不正确,因为从位置 1 到 4,有 4 朵连续的花,而不是 3 朵,所以最终解决方案应该是第 3 天。 - Tianbo
@宗天博 3,2,4 也是连续的。请在问题中更明确地说明什么样的序列才被视为有效。 - גלעד ברקן
@宗天博 或许不仅要比较最后一天,而是要比较最后一个时间间隔 - 因此,如果最后一个时间间隔是 (1,3),则您将不接受 (2,4) 作为 "最后一天",但如果您找到 (4,6),那么您可以更新。这样有帮助吗? - גלעד ברקן

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接