Description:

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:

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

Link:

https://leetcode.com/problems/k-empty-slots/description/

解題方法：

這道題是求在某一天（某次開(kāi)花后）是否有一個(gè)以左右兩朵花為邊界，中間部分不開(kāi)花，并且中間部分長(zhǎng)度為k的區(qū)域。

暴力破解就是按照數(shù)組順序每次迭代開(kāi)一朵花，記錄開(kāi)花位置，每次迭代都掃一遍數(shù)組看看有沒(méi)有符合以上的一段區(qū)域。這樣的時(shí)間復(fù)雜度是O(N^2);

假設(shè)把整個(gè)數(shù)組當(dāng)成一個(gè)大區(qū)域（0到size - 1），以-1和size為邊界；把每次開(kāi)花都當(dāng)成用刀切割當(dāng)前區(qū)域，如果在某次切割后（某日開(kāi)花后）能出現(xiàn)符合上面條件的區(qū)域，那么就找到了這樣一個(gè)天數(shù)。
如果這樣理解，這道題就可以轉(zhuǎn)化為二叉樹(shù)的題來(lái)考慮，如果這道題只是求到這么一個(gè)天數(shù)，用DFS就可以做出來(lái)。如果需要找到最早的天數(shù)，用BFS也可以做出來(lái)。

Tips:

這道題在LeetCode上是要找到最短天數(shù)，所以用BFS。

Time Complexity：

完整代碼：

// DFS:
int kEmptySlots(vector<int>& flowers, int k) {
    int size = flowers.size();
    if(size < 2 || size - 2 < k)
        return -1;
    int result = -1;
    helper(flowers, k, -1, -1, size, result);
    return result;
}
void helper(vector<int>& flowers, int k, int day, int lB, int rB, int& result) {
    if(rB - lB < k + 1 || result != -1 || day >= (int) flowers.size()) {
        return;
    }
    if(rB - lB == k + 1 && lB != -1 && rB != (int) flowers.size()) {
        result = day + 1;
        return;
    }
    int curr = flowers[day + 1] - 1;
    if(curr <= lB || curr >= rB)
        helper(flowers, k, day + 1, lB, rB, result);
    else {
        helper(flowers, k, day + 1, lB, curr, result);
        helper(flowers, k, day + 1, curr, rB, result);
    }
}

// BFS(AC方法):
int kEmptySlots(vector<int>& flowers, int k) {
    int size = flowers.size();
    if(size < 2 || size - 2 < k || k < 0)
        return -1;
    int day = 0;
    queue<pair<int, int>> Q;
    Q.push(pair<int, int> (-1, size));
    while(!Q.empty()) {
        int len = Q.size();
        while(len-- > 0) {
            int l = Q.front().first, r = Q.front().second;
            Q.pop();
            if(r - l < k + 1)
                continue;
            if(r - l == k + 1 && l != -1 && r != size)
                return day;
            int curr = flowers[day] - 1;
            if(curr <= l || curr >= r)
                Q.push(pair<int, int> (l, r));
            else {
                Q.push(pair<int, int> (l, curr));
                Q.push(pair<int, int> (curr, r));
            }

        }
        ++day;
    }
    return -1;
}