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:
Input:
flowers: [1,3,2]
k: 1
Output: 2
Explanation: In the second day, the first and the third flower have become blooming.
intkEmptySlots(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;}
解法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)
publicintkEmptySlots(int[] flowers,int k){int[] days =newint[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;}
publicint kEmptySlots(int[] flowers, int k) {
int[] days = newint[flowers.length];
for (int i = 0; i < flowers.length; i++) days[flowers[i] - 1] = i + 1;
intleft = 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;
}
public int kEmptySlots(int[] flowers, int k) {
int n = flowers.length;
if (n == 1 && k == 0) return1;
TreeSet<Integer> sort = new TreeSet<>();
for (int i = 0; i < n; ++i) {
sort.add(flowers[i]);
Integer min = sort.lower(flowers[i]);
Integer max = sort.higher(flowers[i]);
if (min != null && flowers[i] - min == k + 1) return i + 1;
if (max != null && max - flowers[i] == k + 1) return i + 1;
}
return -1;
}
publicintkEmptySlots(int[] flowers, int k) {
if (flowers.length == 0) return -1;
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < flowers.length; i++) {
set.add(flowers[i]);
int pre = flowers[i] - k - 1, next = flowers[i] + k + 1, tag = 0;
if (pre >= 1 && set.contains(pre)) {
for (int j = pre + 1; j < pre + 1 + k; j++) {
if (set.contains(j)) {
tag = 1;
break;
}
}
if (tag == 0) return i + 1;
}
tag = 0;
if (next <= flowers.length && set.contains(next)) {
for (int j = flowers[i] + 1; j < next; j++) {
while (set.contains(j)) {
tag = 1;
break;
}
}
if (tag == 0) return i + 1;
}
}
return -1;
}
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 indexedprivateint[] bitree;
publicintkEmptySlots(int[] flowers, int k){
int len = flowers.length;
bitree = newint[len + 1];
for (int i = 0; i < len; i++) {
update(1, flowers[i]);
// Compare the flower k distance apart to its rightif (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 leftif (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.
*/privatevoidupdate(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.
*/privateintread(int index){
int sum = 0;
while (index > 0) {
sum += bitree[index];
index -= index & (-index);
}
return sum;
}
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.
publicintkEmptySlots(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// processint[] days = newint[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 dayint 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;
}
