LWC 51：683. K Empty Slots
LWC 51：683. K Empty Slots
LWC 51：683. K Empty Slots
Problem:
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].
题意：
题目要求满足开花的两个slot之间的间隙恰好为k个的天数。
很暴力，遍历每个位置i，因为在位置i的左侧一定都是开花的，而在位置i的右侧则都是还没开过的花。所以在左侧的位置中，找到两个相邻位置之差为k个即可，为了快速比较相邻slot之间的间隙，i在不断累加的同时，始终保持i左侧位置的有序性，在插入的同时，去比较它的左侧位置，和右侧位置，看是否符合间隙之差为k+1。
当然上述操作需要维护位置的有序性，于是采用了插入排序算法，并且输出插入对应的位置。这样就能方便的找寻当前位置的左侧位置和右侧位置。
代码如下：
public int kEmptySlots(int[] flowers, int k) {
int n = flowers.length;
if (n == 1 && k == 0) return 1;
sort = new int[n + 16];
for (int i = 0; i < n; ++i) {
int index = add(flowers[i]);
int min = index - 1 < 0 ? -11111111 : sort[index - 1];
int max = index + 1 >= tot ? -11111111 : sort[index + 1];
if (valid(flowers[i], k, min, max)) return i + 1;
}
return -1;
}
boolean valid(int x, int k, int min, int max) {
if (max - x == k + 1) return true;
if (x - min == k + 1) return true;
return false;
}
int[] sort;
int tot = 0;
public int add(int x) {
int j = 0;
while (j < tot && sort[j] < x) {
++j;
}
for (int i = tot - 1; i >= j; --i) {
sort[i + 1] = sort[i];
}
sort[j] = x;
tot++;
return j;
}当然，你也可以使用JAVA自带的数据结构，TreeSet来实现，代码精简很多。
代码如下：
public int kEmptySlots(int[] flowers, int k) {
int n = flowers.length;
if (n == 1 && k == 0) return 1;
TreeSet<Integer> sort = new TreeSet<>();
for (int i = 0; i < n; ++i) {
sort.add(flowers[i]);
Integer min = sort.lower(flowers[i]);
Integer max = sort.higher(flowers[i]);
int mi = min == null ? -1111111 : min;
int ma = max == null ? -1111111 : max;
if (valid(flowers[i], k, mi, ma)) return i + 1;
}
return -1;
}
boolean valid(int x, int k, int min, int max) {
if (max - x == k + 1) return true;
if (x - min == k + 1) return true;
return false;
}