面试算法题：花园开花场景下寻找大小为K的连续盛开组天数

这题我之前也碰到过类似的，核心思路转个弯就好解决了。先帮你再明确下问题：

现有一个含N个花槽的花园，每个花槽内有一朵花。N朵花将在N天内依次盛开，每天恰好有一朵花盛开，且盛开后持续保持该状态。给定一个由1到N组成的数组flowers，数组中第i个元素表示第i+1天（数组索引从0开始）开花的花槽位置。请找出最早出现连续K个花槽均为盛开状态的天数。

思路拆解 #

首先，我们可以先构建一个开花时间映射数组：创建数组days，其中days[pos]直接表示花槽pos盛开的具体天数。比如flowers[i]是第i+1天开花的花槽，那days[flowers[i]] = i+1（题目里花槽位置是1到N，所以days的索引直接用1到N更方便）。

接下来问题就简化了：在days数组中，所有长度为K的连续子数组里，每个子数组的最大值代表这个区间全部盛开的天数（毕竟最后一朵开的花才会让整个区间都盛开），我们要找这些最大值里的最小值——这就是最早出现连续K个盛开花槽的天数。

高效实现：滑动窗口+单调队列 #

如果用暴力法遍历每个窗口找最大值，时间复杂度是O(N*K)，N大的时候肯定超时。所以我们用单调递减队列来维护窗口内的最大值，把时间复杂度降到O(N)。

具体步骤：

1. 先构建days数组，完成花槽到开花天数的映射。
2. 初始化一个双端队列，用来存储当前窗口内的花槽位置，队列头部始终是当前窗口中开花天数最大的花槽。
3. 遍历每个花槽：
   • 加入新花槽前，把队列中所有开花天数小于当前花槽的元素弹出（它们不可能成为后续窗口的最大值了）。
   • 将当前花槽位置加入队列。
   • 当窗口长度达到K后（也就是遍历到第pos个花槽，pos >= K）：
     • 先把队列头部那些已经不在当前窗口里的花槽位置弹出。
     • 此时队列头部对应的天数就是当前窗口的最大值，用它更新我们的最小结果。
4. 最后得到的最小结果就是答案。

代码示例（Python） #

def earliest_bloom_day(flowers, K):
    N = len(flowers)
    # 构建days数组，花槽位置是1-based
    days = [0] * (N + 1)
    for day, pos in enumerate(flowers, 1):
        days[pos] = day
    
    from collections import deque
    q = deque()
    min_result = float('inf')
    
    for pos in range(1, N+1):
        # 维护单调递减队列：弹出所有比当前days[pos]小的元素
        while q and days[pos] >= days[q[-1]]:
            q.pop()
        q.append(pos)
        
        # 当窗口长度达到K时，开始计算
        if pos >= K:
            # 移除不在当前窗口内的元素
            while q[0] <= pos - K:
                q.popleft()
            # 更新最小结果
            current_max = days[q[0]]
            if current_max < min_result:
                min_result = current_max
    
    return min_result

测试验证 #

比如拿这个测试用例：

• flowers = [1,3,2,5,4], K=2
• 构建的days数组是[0,1,3,2,5,4]
• 遍历窗口得到的最大值分别是3、3、5、5，最小的是3，所以返回3，完全符合预期。

这个方案时间复杂度O(N)，空间复杂度O(K)（队列最多存K个元素），效率拉满。

内容的提问来源于stack exchange，提问作者remif