X

LEETCODE 683. K Empty Slots 解题思路分析

题目大意:

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.

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

View Comments (1)

  • If some one needs to be updated with newest technologies
    afterward he must be pay a visit this site and be up to date
    everyday.