Link: https://leetcode.cn/problems/k-empty-slots/

Question

difficulty: high
adj diff: 5

You have n bulbs in a row numbered from 1 to n. Initially, all the bulbs are turned off. We turn on exactly one bulb every day until all bulbs are on after n days.

You are given an array bulbs of length n where bulbs[i] = x means that on the (i+1)th day, we will turn on the bulb at position x where i is 0-indexed and x is 1-indexed.

Given an integer k, return the minimum day number such that there exists two turned on bulbs that have exactly k bulbs between them that are all turned off. If there isn't such day, return -1.

Example 1:

Input: bulbs = [1,3,2], k = 1
Output: 2
Explanation:
On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.
Example 2:

Input: bulbs = [1,2,3], k = 1
Output: -1

Constraints:

n == bulbs.length
1 <= n <= 2 * 104
1 <= bulbs[i] <= n
bulbs is a permutation of numbers from 1 to n.
0 <= k <= 2 * 104

思路：

  1. 滑动窗口方法。
  2. maintain 一个长度为 k+1 的窗口，其中，所有 boundary 分别在 第 x 天，和第 y 天点亮。
  3. min-heap 中，放入 k-1 个元素，也就是 x 天 和 y 天 中间的所有 bulb
  4. 看看 min-heap 中，最小天数是多少（假设是 w）。
  5. 如果 w > Math.min(x, y)，则说明 [x，y] 就是一个 valid answer：距离为 k，并且中间所有 bulb 都是关灯状态。
  6. (Optionally) 有一种思路，那就是 window 不重叠，下一次只需直接扫描没读过的元素就行了。不过我不是很理解。

Code

TODO