0683：K 个关闭的灯泡（★★）

2016-11-13 约 606 字预计阅读 2 分钟次阅读

力扣第 683 题

题目

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

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

给你一个整数 k ，请返回恰好有两个打开的灯泡，且它们中间正好有 k 个 全部关闭的 灯泡的 最小的天数 。如果不存在这种情况，返回 -1 。

示例 1：

输入：
bulbs = [1,3,2]，k = 1
输出：2
解释：
第一天 bulbs[0] = 1，打开第一个灯泡 [1,0,0]
第二天 bulbs[1] = 3，打开第三个灯泡 [1,0,1]
第三天 bulbs[2] = 2，打开第二个灯泡 [1,1,1]
返回2，因为在第二天，两个打开的灯泡之间恰好有一个关闭的灯泡。

示例 2：

输入：bulbs = [1,2,3]，k = 1
输出：-1

提示：

n == bulbs.length
1 <= n <= 2 * 10⁴
1 <= bulbs[i] <= n
bulbs 是一个由从 1 到 n 的数字构成的排列
0 <= k <= 2 * 10⁴

分析

#1 有序集合

可以用有序集合模拟，看和上/下一个打开灯泡的间隔即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


from sortedcontainers import SortedList
class Solution:
    def kEmptySlots(self, bulbs: List[int], k: int) -> int:
        sl = SortedList()
        for i,b in enumerate(bulbs,1):
            sl.add(b)
            pos = sl.index(b)
            if pos and sl[pos-1]==b-k-1:
                return i
            if pos+1<len(sl) and sl[pos+1]==b+k+1:
                return i
        return -1

323 ms

#2 单调队列

将 bulbs 转为数组 A，A[i] 代表灯泡 i 打开的天数
问题转为求 A 的 k+2 长的子数组，首尾是最小值
可以用单调队列维护 k 长的子数组最小值，和首位比较即可
注意特判 k=0 的情况

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
    def kEmptySlots(self, bulbs: List[int], k: int) -> int:
        n = len(bulbs)
        A = [0]*n
        for i,x in enumerate(bulbs):
            A[x-1] = i+1
        if k==0:
            return min(max(a,b) for a,b in pairwise(A)) if len(A)>=2 else -1
        res = inf
        dq = deque()
        for i,a in enumerate(A):
            if dq and dq[0]==i-k:
                dq.popleft()
            while dq and A[dq[-1]]>a:
                dq.pop()
            dq.append(i)
            if k<=i<n-1 and A[dq[0]]>max(A[i+1],A[i-k]):
                res = min(res,max(A[i+1],A[i-k]))
        return res if res<inf else -1

229 ms

目录

0683：K 个关闭的灯泡（★★）

题目

分析

#1 有序集合

#2 单调队列

解答