题目描述：

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

题目大意：

花园中有N个槽，每次在槽中种一朵花。给定种花的顺序flowers，flowers[i] = x表示第i天，在第x个槽种下一朵花。

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

解题思路：

树状数组（Fenwick Tree）

树状数组ft[k]存储前k个槽一共有多少朵花，则区间[m, n]的花朵总数 = ft[n] - ft[m - 1]

利用该数据结构，遍历flowers即可求解。

Python代码：

class Solution(object):
    def kEmptySlots(self, flowers, k):
        """
        :type flowers: List[int]
        :type k: int
        :rtype: int
        """
        maxn = max(flowers)
        nums = [0] * (maxn + 1)
        ft = FenwickTree(maxn)
        for i, v in enumerate(flowers):
            ft.add(v, 1)
            nums[v] = 1
            if v >= k and ft.sum(v) - ft.sum(v - k - 2) == 2 and nums[v - k - 1]:
                return i + 1
            if v + k + 1<= maxn and ft.sum(v + k + 1) - ft.sum(v - 1) == 2 and nums[v + k + 1]:
                return i + 1
        return -1

class FenwickTree(object):
    def __init__(self, n):
        self.n = n
        self.sums = [0] * (n + 1)
    def add(self, x, val):
        while x <= self.n:
            self.sums[x] += val
            x += self.lowbit(x)
    def lowbit(self, x):
        return x & -x
    def sum(self, x):
        res = 0
        while x > 0:
            res += self.sums[x]
            x -= self.lowbit(x)
        return res

 

本文链接：http://bookshadow.com/weblog/2017/09/24/leetcode-k-empty-slots/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码