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

```    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 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;
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;
}```

```    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) {
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;
}```

0 条评论

• ### LeetCode Weekly Contest 28解题思路

好吧，不要被这道题的例子给骗了。要求输出的最大，意思就是求除第一个元素之外的其他division最小，而不断连除就是第二部分的最小值，所以有如下代码：

• ### LWC 53：694. Number of Distinct Islands

LWC 53：694. Number of Distinct Islands 传送门：694. Number of Distinct Islands Probl...

• ### 挑战程序竞赛系列（35）：3.3Binary Indexed Tree

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### POJ--3321 Apple Tree(树状数组+dfs(序列)）

Apple Tree Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 2...

• ### C# 各种类型的转换

/// <summary> /// 一些常用的方法 /// 1、一些高效的转换方法 /// </summary> public...

• ### ZOJ 3631 Watashi's BG（01dp）

01dp不过由于数组过于大，开不开，学了搜索过了，先记录下 还有一种方法 #include<stdio.h> #include<algorithm> using...

• ### qsort(),sort()排序函数

一.qsort（）函数 功 能： 使用快速排序例程进行排序 头文件：stdlib.h 用 法： void qsort(void *base,int nelem,...

• ### Semaphore流量控制和源码分析

原文链接：https://www.jhonrain.org/2019/09/18/高并发-高并发-Semaphore源码解析和使用场景/

• ### Maximum Depth of Binary Tree

问题：二叉树的最深深度 class Solution { public: void dfs(TreeNode *root,int step,int &M...