0683. K 个关闭的灯泡 #

标签：树状数组、数组、有序集合、滑动窗口
难度：困难

题目大意 #

n 个灯泡排成一行，编号从 1 到 n。最初，所有灯泡都关闭。每天只打开一个灯泡，直到 n 天后所有灯泡都打开。

给定一个长度为 n 的灯泡数组 blubs，其中 bulls[i] = x 意味着在第i + 1 天，我们会把在位置 x 的灯泡打开，其中 i 从 0 开始，x 从 1 开始。

再给定一个整数 k。

要求：输出在第几天恰好有两个打开的灯泡，使得它们中间正好有 k 个灯泡且这些灯泡全部是关闭的。如果不存在这种情况，则返回 -1。如果有多天都出现这种情况，请返回最小的天数。

解题思路 #

blubs[i] 记录的是第 i + 1 天开灯的位置。我们将其转换一下，使用另一个数组 days 来存储每个灯泡的开灯时间，其中 days[i] 表示第 i 个位置上的灯泡的开灯时间。

使用 ans 记录最小满足条件的天数。维护一个窗口 left、right。其中 right = left + k + 1。使得区间 (left, right) 中所有灯泡（总共为 k 个）开灯时间都晚于 days[left] 和 days[right]。
对于区间 [left, right]，left < i < right：
- 如果出现 days[i] < days[left] 或者 days[i] < days[right]，说明不符合要求。将 left、right 移动到 [i, i + k + 1]，继续进行判断。
- 如果对于 left < i < right 中所有的 i，都满足 days[i] >= days[left] 并且 days[i] >= days[right]，说明此时满足要求。将当前答案与 days[left] 和 days[right] 中的较大值作比较。如果比当前答案更小，则更新答案。同时将窗口向右移动 k 位。继续检测新的不相交间隔 [right, right + k + 1]。
  - 注意：之所以检测新的不相交间隔，是因为如果检测的是相交间隔，原来的 right 位置元素仍在区间中，肯定会出现 days[right] < days[right_new]，不满足要求。所以此时相交的区间可以直接跳过，直接检测不相交的间隔。
直到 right >= len(days) 时跳出循环，判断是否有符合要求的答案，并返回答案 ans。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution:
    def kEmptySlots(self, bulbs: List[int], k: int) -> int:
        size = len(bulbs)
        days = [0 for _ in range(size)]
        for i in range(size):
            days[bulbs[i] - 1] = i + 1

        left, right = 0, k + 1
        ans = float('inf')
        while right < size:
            check_flag = True
            for i in range(left + 1, right):
                if days[i] < days[left] or days[i] < days[right]:
                    left, right = i, i + k + 1
                    check_flag = False
                    break
            if check_flag:
                ans = min(ans, max(days[left], days[right]))
                left, right = right, right + k + 1

        if ans != float('inf'):
            return ans
        else:
            return -1