K Empty Slots

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

There is a garden withNslots. In each slot, there is a flower. TheNflowers will bloom one by one inNdays. In each day, there will beexactlyone flower blooming and it will be in the status of blooming since then.

Given an arrayflowersconsists of number from1toN. Each number in the array represents the place where the flower will open in that day.

For example,flowers[i] = xmeans that the unique flower that blooms at dayiwill be at positionx, whereiandxwill be in the range from1toN.

Also given an integerk, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them iskand these flowers are not blooming.

If there isn't such day, output -1.

Example 1:

Input:
 
flowers: [1,3,2]
k: 1

Output:
 2

Explanation:
 In the second day, the first and the third flower have become blooming.

Example 2:

Input:
 
flowers: [1,2,3]
k: 1

Output:
 -1

Note:

1. The given array will be in the range [1, 20000].

Thoughts

题目说明不是很好。大致意思是有n个坑，按照给定数组flowers的元素值顺序每天在对应的坑里种花。问第一次刚好出现间隔k + 1的(中间有k多空花)两朵花时是第几天。

gap的题基本可以用bucket sort解。因此可以把flowers分到大小相同的bucket里，每个bucket大小为k + 1(根据题意是中间有k个empty的slot, 因此位置之差是k + 1)，然后把花按顺序分到这些buckets中，1~k+1在第一个bucket, k+2 ~ 2k + 3在第二个bucket，以此类推。每个bucket维持一个最大值和最小值，出现在同一bucket时的花们间隔肯定不能是k + 1，所以当nums[i]既不是当前bucket k的最大或最小时，可以直接略过。只有当前Bucket的最小值和上一个bucket最大值距离为k + 1时或当前bucket最大值和下一个bucket最小值间隔为k+1时才满足题目要求。时间复杂度O(N).

还可以用BST解，同理维持一个BST每天往里插树节点，节点的值就是坑的位置，插入后分别检查它的前一个和后一个元素是否满足条件即可。由于插入需要log(n)时间，因此总时间复杂度O(nlgn)。

Code

class Solution {
public:
    int kEmptySlots(vector<int> &flowers, int k) {
        const int N = flowers.size();
        const int bnum = (N + K) / (K + 1);
        vector<int> mins(bnum, INT_MAX), maxs(bnum, INT_MIN);
        for (int i = 0; i < N; ++i) {
            const int x = flowers[i];
            const int b = x / (k + 1);
            if (x < mins[b]) {
                mins[b] = x;
                if (p > 0 && mins[b] - maxs[p - 1] == k + 1) return i + 1;
            }
            if (x > maxs[b]) {
                maxs[b] = x;
                if (p < bnum && mins[b + 1] - maxs[b] == k + 1) return i + 1;
            }
        }
        return -1;
    }
};