683. K Empty Slots

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.

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].

My Solutions：

这道题的场景是花园中有N个槽，每次在槽中种一朵花。给定种花的顺序flowers，flowers[i] = x表示第i天，在第x个槽种下一朵花，一旦放了就会一直开下去。其实题目这里有误，数组是从0开始的，而天数和位置都是从1开始的，所以正确的应该是第i+1天放的花会在位置x。 day说是1~N，其实应该是0~N-1。

另外给定数字k，求flowers中是否存在某一天，满足相隔k距离的两个端点恰好各有一朵花，而这两朵花之间的k个槽都没有花。

用一个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即可，

解法一：最优解法，时间复杂度为O(n)，空间复杂度为O(n)，思路是用额外空间记录一下1 ~ n个花槽，是第几天开花。再从头遍历，看看每隔K天两个花槽之间有没有更早的天数，没有则更新result，有则从天数最早的index向后走直到right走到最后。

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