683. 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.
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个槽都没有花。

flowers: 1, 3, 2

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