683 K Empty Slots

这道题目比较难写，有两种思路。

第一种思路：主要的思路是用哈希表或者用数组将原始数据做反映射，得到的数组，我们需要做的就是在数组中，找到长度为k+2的sliding windows, 其中间值小于两边的值的最大值。

第二种思路：使用BST, 使用bisect建立一个二分搜索树，可以使得时间复杂度，空间复杂度降低。

第三种思路：使用Buckets进行分段存储。

class Solution(object):
    def kEmptySlots(self, flowers, k):
        """
        :type flowers: List[int]
        :type k: int
        :rtype: int
        """
        hash = {}
        length = len(flowers)
        for day, position in enumerate(flowers):
            hash[position] = day + 1
        left, right = 1, k+2
        if right > length:
            return -1
        ans = []
        i = left + 1
        while i < length+1:
            if hash[i] > max(hash[left], hash[right]):
                i += 1
                continue
            else:
                if i == right:
                    ans.append(max(hash[left], hash[right]))
                    left = left + 1
                    right = right + 1
                    i = left + 1
                    if right > length:
                        return min(ans) if ans else -1
                else:
                    left = i
                    right = left + k + 1
                    i = left + 1
                    if right > length:
                        return min(ans) if ans else -1

class Solution(object):
    def kEmptySlots(self, flowers, k):
        """
        :type flowers: List[int]
        :type k: int
        :rtype: int
        """
        l = len(flowers)
        if k < 0 or k >= l:
            return -1
        p = (l + k)/(k + 1) ## 将flowers分成p个槽
        part = [[None,None] for i in range(p)] ##对于每个槽，记录每个槽的最低占位和最高占位所在的位置 0 => min 1 => max 
        for i in range(l):
            num = (flowers[i] - 1)/(k + 1)
            if part[num][0] is None or flowers[i] < part[num][0]:
                part[num][0] = flowers[i]
                if num and part[num-1][1] is not None and  part[num][0] - part[num-1][1] == k + 1:
                    return i + 1
            if part[num][1] is None or flowers[i] > part[num][1]:
                part[num][1] = flowers[i]
                if num < p - 1 and part[num+1][0] is not None and part[num+1][0] - part[num][1] == k + 1:
                    return i + 1
        return -1

class Solution(object):
    def kEmptySlots(self, flowers, k):
        """
        :type flowers: List[int]
        :type k: int
        :rtype: int
        """
        active = []
        for day, flower in enumerate(flowers, 1):
            i = bisect.bisect(active, flower)
            for neighbor in active[i-(i>0): i+1]:
                if abs(neighbor - flower) - 1 == k:
                    return day
            active.insert(i, flower)
        return -1