[LeetCode] 683. K Empty Slots

[grandyang]

 

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

 

这道题给了我们这样一个场景，说是花园里有N个空槽，可以放花，每天放一朵开着的花，而且一旦放了就会一直开下去。不是按顺序放花，而是给了我们一个数组 flowers，其中 flowers[i] = x 表示第i天放的花会在位置x。其实题目这里有误，数组是从0开始的，而天数和位置都是从1开始的，所以正确的应该是第 i+1 天放的花会在位置x。然后给了我们一个整数k，让我们判断是否正好有两朵盛开的花中间有k个空槽，如果有，返回当前天数，否则返回-1。博主刚开始想的是先用暴力破解来做，用一个状态数组，如果该位置有花为1，无花为0，然后每增加一朵花，就遍历一下状态数组，找有没有连续k个0，结果TLE了。这说明，应该等所有花都放好了，再来找才行，但是这样仅用0和1的状态数组是不行的，我们得换个形式。

我们用一个 days 数组，其中 days[i] = t 表示在 i+1 位置上会在第t天放上花，那么如果 days 数组为 [1 3 2]，就表示第一个位置会在第一天放上花，第二个位置在第三天放上花，第三个位置在第二天放上花。我们想，在之前的状态数组中，0表示没放花，1表示放了花，而 days 数组中的数字表示放花的天数，那么就是说数字大的就是花放的时间晚，那么在当前时间i，所有大于i的是不是也就是可以看作是没放花呢，这样问题就迎刃而解了，我们来找一个 k+2 大小的子数组，除了首尾两个数字，中间的k个数字都要大于首尾两个数字即可，那么首尾两个数字中较大的数就是当前的天数。left 和 right 是这个大小为 k+2 的窗口，初始化时 left 为0，right 为 k+1，然后i从0开始遍历，这里循环的条件时 right 小于n，当窗口的右边界越界后，循环自然需要停止。如果当 days[i] 小于 days[left]，或者 days[i] 小于等于 days[right] 的时候，有两种情况，一种是i在[left, right]范围内，说明窗口中有数字小于边界数字，这不满足我们之前限定的条件，至于days[i]为何可以等于 days[right]，是因为当i遍历到 right 到位置时，说明中间的数字都是大于左右边界数的，此时我们要用左右边界中较大的那个数字更新结果 res。不管i是否等于 right，只要进了这个if条件，说明当前窗口要么是不合题意，要么是遍历完了，我们此时要重新给 left 和 right 赋值，其中 left 赋值为i，right 赋值为 k+1+i，还是大小为 k+2 的窗口，继续检测。最后我们看结果 res，如果还是 INT_MAX，说明无法找到，返回 -1 即可，参见代码如下：

 

解法一：

class Solution {
public:
    int kEmptySlots(vector<int>& flowers, int k) {
        int res = INT_MAX, left = 0, right = k + 1, n = flowers.size();
        vector<int> days(n, 0);
        for (int i = 0; i < n; ++i) days[flowers[i] - 1] = i + 1;
        for (int i = 0; right < n; ++i) {
            if (days[i] < days[left] || days[i] <= days[right]) {
                if (i == right) res = min(res, max(days[left], days[right]));
                left = i; 
                right = k + 1 + i;
            }
        }
        return (res == INT_MAX) ? -1 : res;
    }
};

 

下面这种方法用到了 TreeSet 来做，利用其自动排序的特点，然后用 lower_bound 和 upper_bound 进行快速的二分查找。 题目中的 flowers[i] = x 表示第 i+1 天放的花会在位置x。所以我们遍历 flowers 数组，其实就是按照时间顺序进行的，我们取出当前需要放置的位置 cur，然后在集合 TreeSet 中查找第一个大于 cur 的数字，如果存在的话，说明两者中间点位置都没有放花，而如果中间正好有k个空位的话，那么当前天数就即为所求。这是当 cur 为左边界的情况，同样，我们可以把 cur 当右边界来检测，在集合 TreeSet 中查找第一个小于 cur 的数字，如果二者中间有k个空位，也返回当前天数。需要注意的是，C++ 和 Java 中的 upper_bound 和 higher 是相同作用的，但是 lower_bound 和 lower 却不太一样。C++ 中的 lower_bound 找的是第一个不小于目标值的数字，所以可能会返回和目标值相同或者大于目标值的数字。只要这个数字不是第一个数字，然后我们往前退一位，就是要求的第一个小于目标值的数字，这相当于 Java 中的 lower 函数，参见代码如下：

 

解法二：

class Solution {
public:
    int kEmptySlots(vector<int>& flowers, int k) {
        set<int> s;
        for (int i = 0; i < flowers.size(); ++i) {
            int cur = flowers[i];
            auto it = s.upper_bound(cur);
            if (it != s.end() && *it - cur == k + 1) {
                return i + 1;
            }
            it = s.lower_bound(cur);
            if (it != s.begin() && cur - *(--it) == k + 1) {
                return i + 1;
            }
            s.insert(cur);
        }
        return -1;
    }
};

 

讨论：这道题有一个很好的 follow up，就是改为最后的有k盆连续开花的是哪一天，就是k个连续不空的槽，博主没有想出特别好的解法，只能采用暴力搜索的解法。比如就像解法一，求出了 days 数组后。我们可以遍历每个长度为k的子数组，然后找出该子数组中最大的数字，然后找出所有的这些最大数字中的最小的一个，就是所求。或者，我们可以使用类似于合并区间的思想，遍历 flowers 数组，每遍历一个数字，如果跟现有的区间连续，就加入当前区间，直到出现某个区间的长度大于等于k了，则当前天数即为所求。如果各位看官大神们有更好的解法，一定要留言告知博主哈～

 

Github 同步地址：

#683

 

参考资料：

https://leetcode.com/problems/k-empty-slots/

https://leetcode.com/problems/k-empty-slots/discuss/107931/JavaC%2B%2B-Simple-O(n)-solution

https://leetcode.com/problems/k-empty-slots/discuss/107960/C%2B%2B-ordered-set-Easy-solution

https://leetcode.com/problems/k-empty-slots/discuss/107948/Iterate-over-time-vs.-iterate-over-position

 

LeetCode All in One 题目讲解汇总(持续更新中...)