関小君刷题记

题目大意：

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 everyday 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, find out 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

Note:

1. 1 <= N <= 20000
2. 1 <= bulbs[i] <= N
3. bulbs is a permutation of numbers from 1 to N.
4. 0 <= K <= 20000

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=683

解题思路分析：

很早就听朋友说起过这道题目，今天随机选题时刚好碰上此题。其实这是一道很有名的问题，记得原题说的是种花问题，也就是本题题目的描述，然后本题的内容却换成了灯泡，没想到Leetcode也玩了一次标题党！不过无所谓，无论是灯泡还是种花对解题思路并没有太大影响。

首先，题目给出了一个数组 bulbs， bulbs[i]代表第i天打开的灯泡编号，我们可以将数组变换为days数组，days[i]代表，打开第2个灯的时间。来看一个例子，比如：

bulbs: [1,3,4,2]

那么：

days: [1,4,2,3]

我们可以定义一个区间，区间长度为k+2，其中k为题目给出的区间长度，该区间内的灯都是关闭状态，另外我们在这个区间两端加上两个端点，这两个端点的灯必须是点亮状态，也就是说，这个 k+2 区间内的灯泡等点亮顺序是，先点亮两个端点，然后再点亮中间的部分。再换句话说，中间部分的点亮时间要晚于两个端点，即在days数组中，中间部分的值应该大于两个端点。因此，当满足该点亮顺序时，该区间为一个合理区间，两个端点后点亮的时间是一个返回结果的候选值。我们用它来更新全局最小值即可。

解题时，我们定义两个指针分别代表区间左端点和右端点，初始时左端点是0，右端点是k+1，此时区间长度是k+2，我们从days数组首位开始向后循环，循环的终止条件是右端点小于数组长度。循环时，若当前下标等于右端点时，代表该区间以遍历结束，为合理区间，利用两个端点的最大值来更新全局最小值。另外，如果当前下标在days数组中的值小于左端点或者右端点在days数组中的值时，说明区间中间某盏灯的点亮时间要早于两个端点，这时不合理区间，此时左区间更新为当前下标，右区间为当前下标加上k再加上1。重复此过程至循环结束，便能遍历出最小时间。

实现代码：

public int kEmptySlots(int[] bulbs, int K) {
    // 将bulbs转为days数组
    // days[i]代表第i个灯泡点亮的时间
    int[] days = new int[bulbs.length];
    for(int i=0;i<bulbs.length;i++){
        days[bulbs[i]-1]=i+1;
    }
    // 返回结果
    int res=Integer.MAX_VALUE;
    // 区间左右端点
    int left=0,right=K+1;
    for(int i=0;right<days.length;i++){
        // 如果当前下标等于右端点
        // 说明当前区间为合理区间
        if(i==right){
            // 两端点最大值为合理解，
            // 利用该解更新全局最小值
            res=Math.min(res,Math.max(days[left],days[right]));
            left=i; // 更新左区间为i
            right=left+K+1; // 更新右区间
            continue;
        }
        // 如果当前下标的值小于两端点的值，说明该区间非法
        if(days[i]<days[left]||days[i]<days[right]){
            left=i; // 更新左区间为i
            right=left+K+1; // 更新右区间
            continue;
        }
    }
    if(res==Integer.MAX_VALUE) return -1;
    return res;
}

本题解法执行时间为5ms。

Runtime: 5 ms, faster than 94.01% of Java online submissions for K Empty Slots.

Memory Usage: 45.2 MB, less than 84.21% of Java online submissions for K Empty Slots.

---

解法二：排序（二分查找）

如果你觉得解法一稍微难于理解，那么我们再来看第二种简单一些的方式，但该方法的缺点是执行效率低于前者，第一种解法的时间复杂度为O(n)，而本解法是O(nlogn)。

我们先建立一个List集合，然后开始循环bulbs数组，按时间顺序遍历每一个点亮灯泡的编号，然后我们使用二分查找，找到该灯泡在List中应该排序的位置，即在List中找到第一个大于当前灯泡下标的位置index，该index是距离当前灯泡左侧最近点亮的灯泡，另外index-1则是右侧最近点亮的灯泡，我们计算出与两侧灯泡的距离（灯泡编号差），如果该距离等于K，那么当前时间点即是返回结果。反之，我们需要继续向后循环，另外不要忘记将当前灯泡插入到List中相应的位置。

本解法中使用到的二分查找思路属于我们之前讲过的 LEETCODE常见算法之二分查找超详细白话讲解 中第五种情况，对于二分查找不熟悉的话，强烈建议查看一下这篇文章。

实现代码：

public int kEmptySlots(int[] bulbs, int K) {
    List<Integer> list=new ArrayList<>();
    for(int i=0;i<bulbs.length;i++){
        int index=binarySearch(list, bulbs[i]);
        if(index>0){
            if(bulbs[i]-list.get(index-1)-1==K){
                return i+1;
            }
        }
        if(index<list.size()){
            if(list.get(index)-bulbs[i]-1==K){
                return i+1;
            }
        }
        list.add(index,bulbs[i]);
    }
    return -1;
}

int binarySearch(List<Integer> list, int bulb){
    int low=0;
    int high=list.size()-1;
    while(low<=high){
        int mid=(low+high)/2;
        if(list.get(mid)>bulb){
            high=mid-1;
        }else{
            low=mid+1;
        }
    }
    return low;
}

本题解法执行时间为73ms。

Runtime: 73 ms, faster than 13.80% of Java online submissions for K Empty Slots.

Memory Usage: 47.3 MB, less than 57.89% of Java online submissions for K Empty Slots.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-683-k-empty-slots-解题思路分析/