## 题目描述：

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

## 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):
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
``````

Pingbacks已关闭。