# K Empty Slots

> There is a garden with`N`slots. In each slot, there is a flower. The`N`flowers will bloom one by one in`N`days. In each day, there will be`exactly`one flower blooming and it will be in the status of blooming since then.
>
> Given an array`flowers`consists of number from`1`to`N`. Each number in the array represents the place where the flower will open in that day.
>
> For example,`flowers[i] = x`means that the unique flower that blooms at day`i`will be at position`x`, where`i`and`x`will be in the range from`1`to`N`.
>
> Also given an integer`k`, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is`k`and 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

```cpp
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;
    }
};
```