题目：
一个花园有N个位置。每个位置上有一朵花。这N朵花会在N天内逐一盛开。每天都一定会有并且只有一朵花盛开，从这天起，这朵花将一直处于盛开的状态。
给定一个由数字1到N组成的数组flowers。数组中的每个数字表示那一天将会盛开的花的位置。
例如，flowers[i] = x表示在位置x上的花会在第i天盛开，其中i和x都在1到N的范围内。
还有，给出一个整数k，你需要返回，在哪一天，恰好有两朵花处于盛开的状态，并且两朵花之间恰好有k朵花没有盛开。
如果有多个答案，选择最小的。
如果不存在这样一天，那么返回-1。
- 给定数组在
[1, 20000]范围内。
样例 1:
输入：[1,2,3,4]，k=1
输出：-1
解释：最先开放的两朵花相邻
样例 2:
输入：[1,3,2]，k=1
输出：2
解释：在第二天，第一朵和第三朵花会开分析：
给定一个开花序列，每天只开一朵花，求两朵花处于盛开时且他们之间恰好有k朵花没有盛开。
第一种思路就是，每开一朵花时，就相应的去检查它前k+1朵花和后k+1朵是否盛开，且他们之间没有花开，如果存在的话返回相应的天数即可。
第二种我们可以用一个有序集合存储每一个开花位置，每新加入到集合中，就检查前一个位置和后一个开花的位置是否符合要求。
第三种我们不存储所有开花位置，而是把开花的位置以K+1为单位分成若干和区间，每个区间只记录当前的最大位置和最小位置。同一个区间内的开花位置是不符合间隔k这个要求，每开一朵花，更新相应区间的最大位置和最小位置，如果是最大位置，那么仅有可能在下一个区间的最大位置符合当前要求，检查即可，同理，如果是最小位置，则仅可能在上一个区间的最小位置符合当前要求。
程序：
C++
class Solution { public: /** * @param flowers: the place where the flower will open in that day * @param k: an integer * @return: in which day meet the requirements */ int kEmptySlots(vector<int> &flowers, int k) { // Write your code here int n = flowers.size(); if(k >= n || n == 0) return -1; set<int> flo; for(int i = 0; i < n; ++i){ int x = flowers[i]; flo.insert(x); auto l = flo.find(x); auto r = l; if(++r != flo.end() && *r == x + k + 1){ return i + 1; } if(l != flo.begin() && *(--l) == x - k - 1){ return i + 1; } } return -1; } };
class Solution { public: /** * @param flowers: the place where the flower will open in that day * @param k: an integer * @return: in which day meet the requirements */ int kEmptySlots(vector<int> &flowers, int k) { // Write your code here int n = flowers.size(); if (n == 0 || k >= n) return -1; int bs = (n - 1) / (k + 1) + 1; vector<int> higher(bs, INT_MIN); vector<int> lower(bs, INT_MAX); for(int i = 0; i < n; ++i){ int x = flowers[i]; int p = (x - 1) / (k + 1); if (x < lower[p]) { lower[p] = x; if (p > 0 && higher[p - 1] == x - k - 1) return i + 1; } if (x > higher[p]) { higher[p] = x; if (p < bs - 1 && lower[p + 1] == x + k + 1) return i + 1; } } return -1; } };
Java
public class Solution { /** * @param flowers: the place where the flower will open in that day * @param k: an integer * @return: in which day meet the requirements */ public int kEmptySlots(int[] flowers, int k) { // Write your code here int n = flowers.length; if(k >= n || n == 0) return -1; TreeSet<Integer> flo = new TreeSet(); for(int i = 0; i < n; ++i){ int x = flowers[i]; flo.add(x); Integer low = flo.lower(x); Integer high = flo.higher(x); if(low != null && low == x - k - 1) return i+1; if(high != null && high == x + k + 1) return i+1; } return -1; } }
public class Solution { /** * @param flowers: the place where the flower will open in that day * @param k: an integer * @return: in which day meet the requirements */ public int kEmptySlots(int[] flowers, int k) { // Write your code here int n = flowers.length; if (n == 0 || k >= n) return -1; int bs = (n - 1) / (k + 1) + 1; int[] higher = new int[bs]; int[] lower = new int[bs]; Arrays.fill(higher, Integer.MIN_VALUE); Arrays.fill(lower, Integer.MAX_VALUE); for(int i = 0; i < n; ++i){ int x = flowers[i]; int p = (x - 1) / (k + 1); if (x < lower[p]) { lower[p] = x; if (p > 0 && higher[p - 1] == x - k - 1) return i + 1; } if (x > higher[p]) { higher[p] = x; if (p < bs - 1 && lower[p + 1] == x + k + 1) return i + 1; } } return -1; } }