http://zxi.mytechroad.com/blog/simulation/leetcode-683-k-empty-slots/
X. Buckets
http://www.cnblogs.com/grandyang/p/8415880.html
https://www.cnblogs.com/lightwindy/p/9727403.html
BST/Buckets
X. TreeSet
http://hanslen.me/2017/11/11/Algorithm-revision/
X.
https://bilbo3000.wordpress.com/2018/02/09/k-empty-slots/
树状数组（Fenwick Tree） 树状数组ft[k]存储前k个槽一共有多少朵花，则区间[m, n]的花朵总数 = ft[n] - ft[m - 1] 利用该数据结构，遍历flowers即可求解。
http://bookshadow.com/weblog/2017/09/24/leetcode-k-empty-slots/
X. BFS
https://www.jianshu.com/p/b958148ea78e
X. Follow up
https://bilbo3000.wordpress.com/2018/02/09/k-empty-slots/
https://lyan62.github.io/leetcode/array/683
讨论：这道题有一个很好的follow up，就是改为最后的有k盆连续开花的是哪一天，就是k个连续不空的槽，博主没有想出特别好的解法，只能采用暴力搜索的解法。比如就像解法一，求出了days数组后。我们可以遍历每个长度为k的子数组，然后找出该子数组中最大的数字，然后找出所有的这些最大数字中的最小的一个，就是所求。或者，我们可以使用类似于合并区间的思想，遍历flowers数组，每遍历一个数字，如果跟现有的区间连续，就加入当前区间，直到出现某个区间的长度大于等于k了，则当前天数即为所求。
X. Videos
花花酱 LeetCode 683. K Empty Slots - 刷题找工作 EP76
30 Min Java Coding Challenge - 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 Ndays. 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:
Example 2:
Note:
- The given array will be in the range [1, 20000].
花园中有N个槽，每次在槽中种一朵花。给定种花的顺序flowers，flowers[i] = x表示第i天，在第x个槽种下一朵花。
另外给定数字k，求flowers中是否存在某一天，满足相隔k距离的两个端点恰好各有一朵花，而这两朵花之间的k个槽都没有花。
int kEmptySlots(vector<int>& flowers, int k) { int n = flowers.size(); if (n == 0 || k >= n) return -1; ++k; int bs = (n + k - 1) / k; vector<int> lows(bs, INT_MAX); vector<int> highs(bs, INT_MIN); for (int i = 0; i < n; ++i) { int x = flowers[i]; int p = x / k; if (x < lows[p]) { lows[p] = x; if (p > 0 && highs[p - 1] == x - k) return i + 1; } if (x > highs[p]) { highs[p] = x; if (p < bs - 1 && lows[p + 1] == x + k) return i + 1; } } return -1; }X.
http://www.cnblogs.com/grandyang/p/8415880.html
这道题给了我们这样一个场景，说是花园里有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即可
https://www.cnblogs.com/lightwindy/p/9727403.html
解法1：先把flowers数组转换成天数的数组，表示某一花槽是哪一天开花的。取第一个花槽位置left和k+1位置的花槽位置right(也就是取一个k+2区间)，然后遍历花槽位置，看有没有比首尾花槽开花更早的(条件是days[i]<left or days[i]<right)，如果有则说明在这个区间形成之前有别的花开了，就不能形成这个k距离的区间，则left变成i，right变成i+k+1，验证下一个区间直到right走到最后。如果i走到位置right同时开花时间正好是days[right]，就找到了一个区间，更新result(更新方法是先取left, right开花时间在后的也就是时间大的，然后如果有多个区间，则取这个满足开花时间早的，也就是开花时间里小的)，这个条件可以和前一个判断写在一起，具体看代码。 T: O(n)，S: O(n)
public int kEmptySlots(int[] flowers, int k) { int[] days = new int[flowers.length]; for (int i = 0; i < flowers.length; i++) days[flowers[i] - 1] = i + 1; int left = 0, right = k + 1, result = Integer.MAX_VALUE; for (int i = 0; right < days.length; i++) { if (days[i] < days[left] || days[i] <= days[right]) { if (i == right) result = Math.min(result, Math.max(days[left], days[right])); left = i; right = k + 1 + i; } } return (result == Integer.MAX_VALUE) ? -1 : result; }
最优解法，时间复杂度为O(n)，空间复杂度为O(n)，思路是用额外空间记录一下1 ~ n个花槽，是第几天开花。再从头遍历，看看每隔K天两个花槽之间有没有更早的天数，没有则更新result，有则从天数最早的index向后走直到right走到最后。
BST/Buckets
X. TreeSet
http://hanslen.me/2017/11/11/Algorithm-revision/
https://blog.csdn.net/katrina95/article/details/79070941public int kEmptySlots(int[] flowers, int k) {TreeSet<Integer> ts = new TreeSet<Integer>();for(int i = 0 ; i < flowers.length; i++){ts.add(flowers[i]);Integer a = ts.lower(flowers[i]);Integer b = ts.higher(flowers[i]);if((a != null && flowers[i]-a-1 ==k) || (b != null && b-flowers[i]-1 == k)){return i+1;//Attention: There is no zero day}}return -1;}
用treemap – 内部排序的hashmap，时间复杂度是O(nlogn)，空间复杂度是O(n)。思路是遍历数组，每次都将花槽编号放进treeset，同时每次都检查到这天为止离此花槽编号最近的花槽编号，如果两个编号之间刚好相差k，那么就返回这时的天数。
X. Brute Force用hashset，从头遍历数组，每次找相距k的花槽编号在不在hashset里，在的话检查直接有没有开花，没有则可以返回，这样的时间复杂度是O(kn)，空间复杂度是O(n)，但是LeetCode里TLE了，不过这里还是放出来吧，拓展一下思路。
public int kEmptySlots(int[] flowers, int k) {
int n = flowers.length;
if (n == 0 || k >= n) return -1;
int[] f = new int[n + 1];
for (int i = 0; i < n; ++i)
if (IsValid(flowers[i], k, n, f))
return i + 1;
return -1;
}
private boolean IsValid(int x, int k, int n, int[] f) {
f[x] = 1;
if (x + k + 1 <= n && f[x + k + 1] == 1) {
boolean valid = true;
for (int i = 1; i <= k; ++i)
if (f[x + i] == 1) {
valid = false;
break;
}
if (valid) return true;
}
if (x - k - 1 > 0 && f[x - k - 1] == 1) {
for (int i = 1; i <= k; ++i)
if (f[x - i] == 1) return false;
return true;
}
return false;
}
X.
https://bilbo3000.wordpress.com/2018/02/09/k-empty-slots/
Let’s say you have an array of integers, you can create a separate BIT to quickly find the sum between the beginning and any given index in O(logn) time. BIT index is 1-based. A node removes its last 1-bit gives its parent. 0110 –> 0100. Each node stores sum in segment (parent, child].
BIT has two methods:
- update(int val, int index)
- Insert an element to the BIT at given index.
- It also updates all nodes “covers” current node.
- Time: O(logn).
- index += index & (-index) to get next node to update. Keep shifting last 1 bit to the left, and clear other 1 bits along the way.
- read(int index)
- Read the prefix sum at given index;
- Time: O(logn).
- index -= index & (-index). Keep trace back through parents and add the sum.
The idea to use BIT in this problem is we going through day by day and insert value 1 and flower position into BIT. This forms a BIT for an arrays of 1s. (1 means bloom and 0 means not bloom). Meanwhile, after each insert at position i, first read prefix sum at
i and i + k + 1 from BIT. If diff is 1, then we found a solution, which is to its right. Otherwise, read prefix sum at i - k - 1 and i. If diff is 1, then we found a solution to its left.
Time: O(nlogn), worst case insert each element in BIT
// Binary index tree is 1 indexed
private int[] bitree;
public int kEmptySlots(int[] flowers, int k) {
int len = flowers.length;
bitree = new int[len + 1];
for (int i = 0; i < len; i++) {
update(1, flowers[i]);
// Compare the flower k distance apart to its right
if (flowers[i] + k + 1 <= len) {
if (read(flowers[i] + k + 1) - read(flowers[i]) == 1) {
return i + 1;
}
}
// Compare the flower k distance apart to its left
if (flowers[i] - k - 1 >= 1) {
if (read(flowers[i]) - read(flowers[i] - k - 1) == 1) {
return i + 1;
}
}
}
return -1;
}
/*
* Binary index tree update method.
* It adds given value to the given node and all
* the nodes that "cover" it.
*/
private void update(int val, int index) {
while (index < bitree.length) {
bitree[index] += val;
index += index & (-index);
}
}
/*
* Binary index tree read method.
* It returns the prefix sum of a given index.
*/
private int read(int index) {
int sum = 0;
while (index > 0) {
sum += bitree[index];
index -= index & (-index);
}
return sum;
}
树状数组（Fenwick Tree） 树状数组ft[k]存储前k个槽一共有多少朵花，则区间[m, n]的花朵总数 = ft[n] - ft[m - 1] 利用该数据结构，遍历flowers即可求解。
X. BFS
https://www.jianshu.com/p/b958148ea78e
这道题是求在某一天（某次开花后）是否有一个以左右两朵花为边界，中间部分不开花，并且中间部分长度为k的区域。
暴力破解就是按照数组顺序每次迭代开一朵花，记录开花位置，每次迭代都扫一遍数组看看有没有符合以上的一段区域。这样的时间复杂度是O(N^2);
假设把整个数组当成一个大区域（0到size - 1），以-1和size为边界；把每次开花都当成用刀切割当前区域，如果在某次切割后（某日开花后）能出现符合上面条件的区域，那么就找到了这样一个天数。
如果这样理解，这道题就可以转化为二叉树的题来考虑，如果这道题只是求到这么一个天数，用DFS就可以做出来。如果需要找到最早的天数，用BFS也可以做出来。
暴力破解就是按照数组顺序每次迭代开一朵花，记录开花位置，每次迭代都扫一遍数组看看有没有符合以上的一段区域。这样的时间复杂度是O(N^2);
假设把整个数组当成一个大区域（0到size - 1），以-1和size为边界；把每次开花都当成用刀切割当前区域，如果在某次切割后（某日开花后）能出现符合上面条件的区域，那么就找到了这样一个天数。
如果这样理解，这道题就可以转化为二叉树的题来考虑，如果这道题只是求到这么一个天数，用DFS就可以做出来。如果需要找到最早的天数，用BFS也可以做出来。
Tips:
这道题在LeetCode上是要找到最短天数，所以用BFS。
//DFS:
int kEmptySlots(vector<int>& flowers, int k) {
int size = flowers.size();
if(size < 2 || size - 2 < k)
return -1;
int result = -1;
helper(flowers, k, -1, -1, size, result);
return result;
}
void helper(vector<int>& flowers, int k, int day, int lB, int rB, int& result) {
if(rB - lB < k + 1 || result != -1 || day >= (int) flowers.size()) {
return;
}
if(rB - lB == k + 1 && lB != -1 && rB != (int) flowers.size()) {
result = day + 1;
return;
}
int curr = flowers[day + 1] - 1;
if(curr <= lB || curr >= rB)
helper(flowers, k, day + 1, lB, rB, result);
else {
helper(flowers, k, day + 1, lB, curr, result);
helper(flowers, k, day + 1, curr, rB, result);
}
}
//BFS(AC方法):
int kEmptySlots(vector<int>& flowers, int k) {
int size = flowers.size();
if(size < 2 || size - 2 < k || k < 0)
return -1;
int day = 0;
queue<pair<int, int>> Q;
Q.push(pair<int, int> (-1, size));
while(!Q.empty()) {
int len = Q.size();
while(len-- > 0) {
int l = Q.front().first, r = Q.front().second;
Q.pop();
if(r - l < k + 1)
continue;
if(r - l == k + 1 && l != -1 && r != size)
return day;
int curr = flowers[day] - 1;
if(curr <= l || curr >= r)
Q.push(pair<int, int> (l, r));
else {
Q.push(pair<int, int> (l, curr));
Q.push(pair<int, int> (curr, r));
}
}
++day;
}
return -1;
}
X. Follow up
https://bilbo3000.wordpress.com/2018/02/09/k-empty-slots/
This is a follow up question. Instead of finding two flowers with k empty slots in between, this problem is regarding find the last day where exact k consecutive flowers bloom.
The solution is very similar to the first problem using two pointers and sliding window. The idea is to maintain a sliding window [l, r] where [l + 1, r – 1] all bloom in earlier days than [l] and [r]. Therefore, need to build an array “days” where days[i] means at position i, which position flower bloom. Note that “sliding window” needs to work on physical positions, thus need to convert from temporal array to spatial array.
Because the consecutive blooms can at the edge. Add one padding on each end of days array can simplify the processing. Initialize with Integer.MAX_VALUE pretend never bloom.
public int kEmptySlots(int[] flowers, int k) {
// Build a days array to store which day a position flower bloom
// Create an extra slot at the beginning and end make it easy to
// process
int[] days = new int[flowers.length + 2];
days[0] = Integer.MAX_VALUE;
days[days.length - 1] = Integer.MAX_VALUE;
for (int i = 0; i < flowers.length; i++) {
int day = i + 1;
int pos = flowers[i];
days[pos] = day;
}
// Two pointers of the window
// Our goal is to find [l + 1, r - 1] that all bloom
// but l and r do not not bloom.
// a.k.a [l + 1, r - 1] must have smaller days than l and r.
int l = 0;
int r = k + 1;
for (int i = 1; i < days.length; i++) {
if (i == r || i == days.length - 1) {
// Found a solution, go through the days in the window
// and find the largest day
int max = Integer.MIN_VALUE;
for (int j = l + 1; j < i; j++) {
max = Math.max(max, days[j]);
}
return max;
} else {
if (days[i] >= days[l] || days[i] >= days[r]) {
// Found flower i in the window that bloom later than two ends
// thus flower i cannot be in the window
// Advance left pointer to i
l = i;
r = l + k + 1;
if (r >= days.length) {
// Cannot find a solution
break;
}
}
}
}
return -1;
}
https://lyan62.github.io/leetcode/array/683
讨论：这道题有一个很好的follow up，就是改为最后的有k盆连续开花的是哪一天，就是k个连续不空的槽，博主没有想出特别好的解法，只能采用暴力搜索的解法。比如就像解法一，求出了days数组后。我们可以遍历每个长度为k的子数组，然后找出该子数组中最大的数字，然后找出所有的这些最大数字中的最小的一个，就是所求。或者，我们可以使用类似于合并区间的思想，遍历flowers数组，每遍历一个数字，如果跟现有的区间连续，就加入当前区间，直到出现某个区间的长度大于等于k了，则当前天数即为所求。
X. Videos
花花酱 LeetCode 683. K Empty Slots - 刷题找工作 EP76
30 Min Java Coding Challenge - K Empty Slots
