开花位置相隔 k 个空槽

开花位置相隔k个空槽

https://leetcode.com/problems/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:

The given array will be in the range [1, 20000].

用set查看前后位置，O(nlgn)

int kEmptySlots(vector<int> &flowers, int k) {
    const int N = flowers.size();
    set<int> st;
    for (int i = 1; i <= N; i++) {
        int pos = flowers[i-1];
        st.insert(pos);
        // 看前后位置是否相隔k
        auto it = st.find(pos);
        if (it != st.begin() && pos - *prev(it) - 1 == k) return i;
        if (next(it) != st.end() && *next(it) - pos - 1 == k) return i;
    }
    return -1;
}

桶排序，O(n)

int kEmptySlots(vector<int> &flowers, int k) {
    const int N = flowers.size();
    // 桶排序，每个桶对应k+1个位置，
    // 这样所找的k个空槽两端有花的情况就不可能出现在桶内，而只能在桶间
    // 每个桶保留最大最小值
    unordered_map<int, vector<int>> buckets; // bucketIdx=>[minOfBucket,maxOfBucket]
    for (int i = 1; i <= N; i++) {
        int pos = flowers[i-1];
        int idx = pos / (k + 1);
        if (buckets.count(idx)) {
            buckets[idx][0] = min(buckets[idx][0], pos);
            buckets[idx][1] = max(buckets[idx][1], pos);
        } else {
            buckets[idx] = {pos, pos};
        }
        // 查看左右桶边界
        if (pos == buckets[idx][0] && buckets.count(idx-1) && pos - buckets[idx-1][1] - 1 == k) return i;
        if (pos == buckets[idx][1] && buckets.count(idx+1) && buckets[idx+1][0] - pos - 1 == k) return i;
    }
    return -1;
}

algo-aha

开花位置相隔k个空槽