滑动窗口算法：LeetCode K空槽变种——寻找连续k朵盛开花的最晚日期

阿华AIGC实验室

2026-5-19

解法：找出存在孤立k朵连续盛开花朵的最晚日期（LeetCode K Empty Slot变种）

这道题是经典K Empty Slot问题的变种——原问题找最早出现连续k朵盛开的日期，而这里我们要找最晚出现「孤立连续k朵」（即窗口左右无盛开花朵或为边界）的日期，要求时间复杂度O(nlogn)，空间复杂度O(n)。

问题明确

给定n朵花，每朵花对应唯一的盛开日期bloomDay[i]（0-based索引），我们需要找到最大的日期D，满足：

存在一个长度为k的连续窗口[i, i+k-1]，窗口内所有花的盛开日期≤D；
若i>0，则bloomDay[i-1] > D（窗口左邻未盛开）；
若i+k <n，则bloomDay[i+k] > D（窗口右邻未盛开）。

核心思路

我们可以通过以下步骤解决：

预处理窗口最大值：用线段树预处理所有长度为k的窗口内的最大盛开日期，这样可以在O(logn)时间内快速查询任意窗口的最大值。
枚举所有候选窗口：遍历每个长度为k的窗口，检查其左右邻居的盛开日期是否大于窗口最大值。如果满足条件，该窗口的最大值就是一个候选答案。
取候选最大值：所有符合条件的候选中的最大值就是我们要找的最晚日期。

线段树的实现保证了时间复杂度稳定在O(nlogn)，完全符合题目要求。

具体实现步骤

1. 构建线段树

线段树的每个节点存储对应区间的最大盛开日期。构建过程时间复杂度O(n)，查询任意区间最大值的时间复杂度O(logn)。

2. 遍历所有窗口

对于每个窗口起始索引i（范围0 ≤ i ≤ n-k）：

查询窗口[i, i+k-1]的最大日期current_max；
检查左边界：若i>0，则需bloomDay[i-1] > current_max；若i=0，左边界条件自动满足；
检查右边界：若i+k <n，则需bloomDay[i+k] > current_max；若i+k =n，右边界条件自动满足；
如果左右条件都满足，将current_max加入候选集合。

3. 确定最终答案

候选集合中的最大值就是我们要找的最晚日期。如果没有候选（即从未出现过孤立的连续k朵），则返回-1。

示例验证

以用户给出的示例为例：

n=7，k=3，bloomDay = [3,1,2,6,4,5,7]
所有长度为3的窗口：
- 窗口[0,2]：max=3，左边界无，右邻bloomDay[3]=6>3，符合条件，候选3；
- 窗口[1,3]：max=6，左邻bloomDay[0]=3≤6，不符合；
- 窗口[2,4]：max=6，左邻bloomDay[1]=1≤6，右邻bloomDay[5]=5≤6，不符合；
- 窗口[3,5]：max=6，左邻bloomDay[2]=2≤6，右邻bloomDay[6]=7>6，符合条件，候选6；
- 窗口[4,6]：max=7，左邻bloomDay[3]=6≤7，不符合；
候选最大值为6，与用户示例的结果一致。

代码示例（Python）

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [0] * (2 * self.size)
        # 填充叶子节点
        for i in range(self.n):
            self.tree[self.size + i] = data[i]
        # 构建线段树
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = max(self.tree[2 * i], self.tree[2 * i + 1])
    
    def query_max(self, l, r):
        # 查询[l, r]区间的最大值，0-based闭区间
        res = 0
        l += self.size
        r += self.size
        while l <= r:
            if l % 2 == 1:
                res = max(res, self.tree[l])
                l += 1
            if r % 2 == 0:
                res = max(res, self.tree[r])
                r -= 1
            l >>= 1
            r >>= 1
        return res

def find_last_k_empty_slot(bloomDay, k):
    n = len(bloomDay)
    if n < k:
        return -1
    st = SegmentTree(bloomDay)
    max_day = -1
    for i in range(n - k + 1):
        current_max = st.query_max(i, i + k - 1)
        # 检查左边界
        left_ok = True
        if i > 0 and bloomDay[i-1] <= current_max:
            left_ok = False
        # 检查右边界
        right_ok = True
        if i + k < n and bloomDay[i+k] <= current_max:
            right_ok = False
        if left_ok and right_ok:
            max_day = max(max_day, current_max)
    return max_day if max_day != -1 else -1

# 测试用户示例
bloomDay = [3,1,2,6,4,5,7]
k=3
print(find_last_k_empty_slot(bloomDay, k)) # 输出6