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.
nFor 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:
The given array will be in the range [1, 20000].
一刷
题解：
花园中有N个槽，每次在槽中种一朵花。给定种花的顺序flowers，flowers[i] = x表示第i天，在第x个槽种下一朵花。
另外给定数字k，求flowers中是否存在某一天，满足相隔k距离的两个端点恰好各有一朵花，而这两朵花之间的k个槽都没有花。
sliding window:
首先构造数组days， days[position] = i, 表示position开花的日子。
然后用left, right表示sliding window的左右边界。然后如果中间存在一个点，开花在days[left], days[right]之前，那么这个sliding window不满足条件。平移到left = i
class Solution {
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 min = Integer.MAX_VALUE;
int left = 0, right = k+1;
for(int i=1; right<days.length; i++){
if(days[i]<days[left] || days[i]<=days[right]){
if(i == right){
min = Math.min(min, Math.max(days[left], days[right]));
}
left = i;
right = left + k+1;
}
}
return (min == Integer.MAX_VALUE)?-1:min;
}
}
