KEmptySlots [source code]
import java.io.*;
public class KEmptySlots {
static
/******************************************************************************/
class Solution {
public int kEmptySlots(int[] flowers, int k) {
int N = flowers.length;
if (N == 0 || k > N - 2)
return -1;
Interval root = new Interval (0, N + 1);
Queue<Interval> queue = new LinkedList<> ();
List<Integer> res = new LinkedList<> ();
queue.offer (root);
outer: for (int i = 0; i < N; i++) {
int pos = flowers[i];
Queue<Interval> next_queue = new LinkedList<> ();
while (!queue.isEmpty ()) {
Interval cur = queue.poll ();
if (cur.start <= pos && cur.end >= pos) {
if (pos - cur.start + 1 >= k + 2) {
if (pos - cur.start + 1 == k + 2 && cur.start > 0) {
res.add (i + 1);
break outer;
}
else
next_queue.offer (new Interval (cur.start, pos));
}
if (cur.end - pos + 1 >= k + 2) {
if (cur.end - pos + 1 == k + 2 && cur.end < N + 1) {
res.add (i + 1);
break outer;
}
else
next_queue.offer (new Interval (pos, cur.end));
}
} else {
next_queue.offer (cur);
}
}
queue = next_queue;
}
return res.size () > 0 ? res.get (0) : -1;
}
static class Interval {
int start, end;
Interval (int s, int e) {
this.start = s;
this.end = e;
}
public String toString () {
return String.format ("[%d, %d]", start, end);
}
}
}
/******************************************************************************/
public static void main(String[] args) {
KEmptySlots.Solution tester = new KEmptySlots.Solution();
int[][] inputs = {
{1,3,2}, {1,2},
{1,2,3}, {1,-1},
{3,1,5,4,2},{1,2},
{6,5,8,9,7,1,10,2,3,4}, {2, 8},
{5,39,25,28,16,58,70,29,67,24,78,13,9,64,98,38,44,96,27,88,75,84,69,34,55,12,47,33,77,15,31,74,2,26,76,10,17,72,100,36,6,90,4,95,49,21,94,79,62,32,1,35,60,18,3,53,82,48,54,30,19,87,40,85,68,57,11,42,92,61,71,37,14,51,50,83,22,93,91,65,99,52,7,46,89,80,20,8,97,86,23,66,81,59,56,63,43,41,73,45}, {4, 17},
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
int[] flowers = inputs[2 * i];
int k = inputs[2 * i + 1][0], ans = inputs[2 * i + 1][1], output = tester.kEmptySlots (flowers, k);
System.out.printf ("%s and %d -> %s, expected: %d\n",
Printer.array (flowers), k, Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
runFileTest (tester, "data/KEmptySlots");
}
static void runFileTest (KEmptySlots.Solution tester, String file_path) {
File dir = new File (file_path);
File[] files = dir.listFiles ((d, name) -> name.matches ("Test.*"));
int count = 0;
for (File file : files) {
System.out.println (Printer.separator ());
try (BufferedReader br = new BufferedReader (new FileReader (file))) {
String line = "";
line = br.readLine ();
String[] tokens = line.replace ("[", "").replace ("]", "").split ("\\,");
int[] flowers = new int[tokens.length];
for (int i = 0; i < tokens.length; i++)
flowers[i] = Integer.parseInt (tokens[i]);
line = br.readLine ();
int k = Integer.parseInt (line);
line = br.readLine ();
int ans = Integer.parseInt (line);
int output = tester.kEmptySlots (flowers, k);
System.out.printf ("BIG TEST #%d:\nlength: %d, k=%d -> %s, expected: %d\n",
++count, flowers.length, k, Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
} catch (Exception e) {
System.out.printf ("Error for test file %s\n", file.getName ());
e.printStackTrace ();
}
}
}
}
题目意思还是很明确的, 因为急着要做这一题, 所以大概思考一下;
另外这题的变形是, 如果让你输出是last day, rather than first day, 怎么写;
这题实际上本身是没有限定说是first occurrence还是last occurrence的, 但是试了一下OJ, 返回的是first;
时间紧张, 没有特别好的办法; 一个比较好的思路是存interval, 就按照这个先写写看;
最后想了其实是一个我个人认为还比较好的算法:
class Solution {
public int kEmptySlots(int[] flowers, int k) {
int N = flowers.length;
if (N == 0 || k > N - 2)
return -1;
// if (k == 0) // TODO
Interval root = new Interval (0, N + 1);
Queue<Interval> queue = new LinkedList<> ();
List<Integer> res = new LinkedList<> ();
queue.offer (root);
outer: for (int i = 0; i < N; i++) {
int pos = flowers[i];
Queue<Interval> next_queue = new LinkedList<> ();
while (!queue.isEmpty ()) {
Interval cur = queue.poll ();
if (cur.start <= pos && cur.end >= pos) {
if (pos - cur.start + 1 >= k + 2) {
if (pos - cur.start + 1 == k + 2 && cur.start > 0)
res.add (i + 1);
else
next_queue.offer (new Interval (cur.start, pos));
}
if (cur.end - pos + 1 >= k + 2) {
if (cur.end - pos + 1 == k + 2 && cur.end < N + 1)
res.add (i + 1);
else
next_queue.offer (new Interval (pos, cur.end));
}
} else {
next_queue.offer (cur);
}
}
queue = next_queue;
}
return res.size () > 0 ? res.get (0) : -1;
}
static class Interval {
int start, end;
Interval (int s, int e) {
this.start = s;
this.end = e;
}
public String toString () {
return String.format ("[%d, %d]", start, end);
}
}
}
但是这个算法, 在bigtest1, 是TLE了(结果是对的), 这个就没有办法了, 可能是算法本身性能有什么瓶颈;
这个时候其实已经知道正确的做法了, 然后大概想了一下, 为什么我这个算法比treeset那个方法慢这么多? 一个可能性是, treeset那个方法, 其实每次当你插入一个数字的时候, 你只需要看两头, 这个等价于在我的方法当中, 你只需要观察自己所在的这个interval; 但是我这里的这个方法其实并没有做到这一点: 我这里实际上在每一个iteration, 是所有的interval都要看一遍, 尽管最后被split的只有其中的一个;
但是为什么我这个算法就一定不满足NlgN呢? 能够证明吗? 每一个iteration的复杂度是当前所有的interval的数量, 那么有多少个呢? 或者说N个iteration所有的number of intervals全都加起来的worst case是多少?
一开始是1个, 然后最后一个iteration, 肯定是N个, 然后height是N, 所以最后基本可以确定我这个算法的复杂度是N^2; 这个还真的是一个不太好意识到的坑;
那么这题基本就这样了, 本来以为看起来挺聪明的一个算法, 居然完全不够复杂度的要求, 难怪是一个hard的题目;
最后发现我上面的算法有一个很严重的问题, 因为我当时在准备的是一个variation: return the last day rather than the first, 所以我上面的代码选择返回所有的结果; 实际上这题因为只要first, 所以可以premature exit; 然后改了一下, 果然就可以AC了, 速度是24ms (58%).
那么为什么这个方法被认为是NlgN呢? 根据上面的分析, 我认为应该是N^2啊, 很奇怪;
editorial
Approach #1: Insert Into Sorted Structure [Accepted]
Intuition
Let's add flowers in the order they bloom. When each flower blooms, we check it's neighbors to see if they can satisfy the condition with the current flower.
这个实际上是这一题最intuitive的思路, 不过就是感觉实现不知道怎么实现最好;
Algorithm
We'll maintain active, a sorted data structure containing every flower that has currently bloomed. When we add a flower to active, we should check it's lower and higher neighbors. If some neighbor satisfies the condition, we know the condition occurred first on this day.
class Solution {
public int kEmptySlots(int[] flowers, int k) {
TreeSet<Integer> active = new TreeSet();
int day = 0;
for (int flower: flowers) {
day++;
active.add(flower);
Integer lower = active.lower(flower)
Integer higher = active.higher(flower);
if (lower != null && flower - lower - 1 == k ||
higher != null && higher - flower - 1 == k)
return day;
}
return -1;
}
}
知道了思路之后, 关键就是这个sorted的结构怎么维护了; 这里可以看到, 人家就是找到了一个更牛逼的轮子; 这个treeset是一个红黑树的实现, 本身就是支持耕种lgN的操作的;
利用了这里的treeset本身的性能, 这个算法是很轻松的就是NlgN;
Approach #2: Min Queue [Accepted]
Intuition
For each contiguous block ("window") of k positions in the flower bed, we know it satisfies the condition in the problem statement if the minimum blooming date of this window is larger than the blooming date of the left and right neighbors.
这个思路很奇特, 直接分析一个k-window本身; 这里的思路确实也是没有问题的: 如果这个window的第一个参与者是在这个window两头的分界的flower都已经bloom之后才bloom, 那么这个window肯定就符合要求;
Because these windows overlap, we can calculate these minimum queries more efficiently using a sliding window structure.
这个说起来简单, 真正实现起来还不知道是怎么回事;
Algorithm
Let days[x] = i be the time that the flower at position x blooms. For each window of k days, let's query the minimum of this window in (amortized) constant time using a MinQueue, a data structure built just for this task. If this minimum is larger than it's two neighbors, then we know this is a place where "k empty slots" occurs, and we record this candidate answer.
To operate a MinQueue, the key invariant is that mins will be an increasing list of candidate answers to the query MinQueue.min.
For example, if our queue is [1, 3, 6, 2, 4, 8], then mins will be [1, 2, 4, 8]. As we MinQueue.popleft, mins will become [2, 4, 8], then after 3 more popleft's will become [4, 8], then after 1 more popleft will become [8].
As we MinQueue.append, we should maintain this invariant. We do it by popping any elements larger than the one we are inserting. For example, if we appended 5 to [1, 3, 6, 2, 4, 8], then mins which was [1, 2, 4, 8] becomes [1, 2, 4, 5].
Note that we used a simpler variant of MinQueue that requires every inserted element to be unique to ensure correctness. Also, the operations are amortized constant time because every element will be inserted and removed exactly once from each queue.
这个解释的感觉不是特别好, 完全就是从imperative的角度去解释这个queue的作用, 至于declarative的角度的原理, 没有给出足够的解释;
class Solution {
public int kEmptySlots(int[] flowers, int k) {
int[] days = new int[flowers.length];
for (int i = 0; i < flowers.length; i++) {
days[flowers[i] - 1] = i + 1;
}
MinQueue<Integer> window = new MinQueue();
int ans = days.length;
for (int i = 0; i < days.length; i++) {
int day = days[i];
window.addLast(day);
if (k <= i && i < days.length - 1) {
window.pollFirst();
if (k == 0 || days[i-k] < window.min() && days[i+1] < window.min()) {
ans = Math.min(ans, Math.max(days[i-k], days[i+1]));
}
}
}
return ans < days.length ? ans : -1;
}
}
class MinQueue<E extends Comparable<E>> extends ArrayDeque<E> {
Deque<E> mins;
public MinQueue() {
mins = new ArrayDeque<E>();
}
@Override
public void addLast(E x) {
super.addLast(x);
while (mins.peekLast() != null &&
x.compareTo(mins.peekLast()) < 0) {
mins.pollLast();
}
mins.addLast(x);
}
@Override
public E pollFirst() {
E x = super.pollFirst();
if (x == mins.peekFirst()) mins.pollFirst();
return x;
}
public E min() {
return mins.peekFirst();
}
}
这个方法的一个小缺点好像就是这个window要从头走到位, 不能premature exit;
注意他主函数里面, i和day标记的都是类似sliding window里面j的位置, 也就是末尾, 或者说next to add的位置; 因为这样的设计, 一开始的k个i, 实际上是一个类似no-op, 或者说init的操作: 就是在先填满window;
然后先看主函数:
Your input
[6,5,8,9,7,1,10,2,3,4]
2
Your stdout
i:(0), flower: (1), day:(6), [6], mins: [6]
i:(1), flower: (2), day:(8), [6, 8], mins: [6, 8]
i:(2), flower: (3), day:(9), [8, 9], mins: [8, 9]
i:(3), flower: (4), day:(10), [9, 10], mins: [9, 10]
i:(4), flower: (5), day:(2), [10, 2], mins: [2]
i:(5), flower: (6), day:(1), [2, 1], mins: [1]
i:(6), flower: (7), day:(5), [1, 5], mins: [1, 5]
i:(7), flower: (8), day:(3), [5, 3], mins: [3]
i:(8), flower: (9), day:(4), [3, 4], mins: [3, 4]
i:(9), flower: (10), day:(7), [3, 4, 7], mins: [3, 4, 7]
首先整个逻辑是跟sliding window非常类似的, i就是类似于我们之前用的j的位置, 每一个iteration, 在这个题目的设定下, 可以直接将这个peek先add进去到window里面, 然后如果i足够大, 因为维护的是一个固定size的window, 所以就可以直接把first给去掉了, 类似于退款;
注意他这里window维护的是全gap, 是不带两头的端点的, 比如这个例子里面, window的长度维护的就是k=2; 类似的, 他判断当i == N - 1的时候, 就不用append了, 因为确实没用: 右端点不可能有flower;
然后调整window的代码里面逻辑就比较简单了, 直接就去去掉first, 然后判断i-k and i+1这两个位置跟当前window的关系(可以通过i=2的例子来验证这个坐标计算); 然后就是query min, 查出来之后跟两头这两个邻居进行比较: 如果比较成功(比两个都小), 那么取两者max(因为这个时候两头才都已经bloom, 这样这个window才是一个名副其实的k-sized gap); 更新ans就行了;
然后就是看这个minqueue本身具体是怎么实现的; 先不看代码, 通过上面的trace看看他到底是在干什么;
running minimum
首先, 这里为什么要extend dequeue? 事实上就是因为想要表达一个window而已; Deque这个接口本身实现的很方便, 所以直接用这个现成的就行了; super里面怎么维护这个Deque本身, 我们不用管;
然后我们extend了之后, 要加一个mins, 这个就是用来维护running minimum的; 光维护window本身还不够, 还要多维护一个数据结构; 关于这个设计的原理, 这个代码本身是很好的, 但是awice说的有问题, 这个mins的head, 始终是当前window的最小值, 这个是没有问题的; awice只解释了这个mins需要维护升序, 但是他没有解释为什么: 这是因为每次我们append的时候, 这个从last位置新add进来的, 可以从后面开始把所有比自己大的都pop掉: 因为我们只要维护min: 在选择min的过程中, 这些larger的数字, 永远不会比我这个新数字更好用: anything they can do, I can do better! 用这个思路, 最后事实上确实是维护了升序, 但是目的上不是这么理解的;
当然, 最简单的另外一个问题: 为什么需要维护一个队列, 而不是一个min数字就行了? 因为你remove first的时候, 加入Poll掉的是min数字本身, 你后面怎么办? 所以必须要维护一个队列;
这个东西还是非常有意思的, 虽然awice本身的解释不是非常到位;
这个算法最后的复杂度是O(N); 另外, 思考角度也很奇特, 直接分析flower bed的时间属性, 而不是按照正常的时间轴模拟的思路;
Approach #3: Sliding Window [Accepted]
Intuition
As in Approach #2, we have days[x] = i for the time that the flower at position x blooms. We wanted to find candidate intervals [left, right] where days[left], days[right] are the two smallest values in [days[left], days[left+1], ..., days[right]], and right - left = k + 1.
这个解读没有问题, 跟上一个做法的核心思路是类似的;
Notice that these candidate intervals cannot intersect: for example, if the candidate intervals are [left1, right1] and [left2, right2] with left1 < left2 < right1 < right2, then for the first interval to be a candidate, days[left2] > days[right1]; and for the second interval to be a candidate, days[right1] > days[left2], a contradiction.
这个是通过额外的观察来简化题目, 不过这个规律本身藏的比较深;
That means whenever whether some interval can be a candidate and it fails first at i, indices j < i can't be the start of a candidate interval. This motivates a sliding window approach.
Algorithm
As in Approach #2, we construct days.
Then, for each interval [left, right] (starting with the first available one), we'll check whether it is a candidate: whether days[i] > days[left] and days[i] > days[right] for left < i < right.
If we fail, then we've found some new minimum days[i] and we should check the new interval [i, i+k+1]. If we succeed, then it's a candidate answer, and we'll check the new interval [right, right+k+1].
很聪明的思路;
class Solution {
public int kEmptySlots(int[] flowers, int k) {
int[] days = new int[flowers.length];
for (int i = 0; i < flowers.length; i++) {
days[flowers[i] - 1] = i + 1;
}
int ans = Integer.MAX_VALUE;
int left = 0, right = k+1;
search: while (right < days.length) {
for (int i = left+1; i < right; ++i) {
if (days[i] < days[left] || days[i] < days[right]) {
left = i;
right = i + k + 1;
continue search;
}
}
ans = Math.min(ans, Math.max(days[left], days[right]));
left = right;
right = left + k + 1;
}
return ans < Integer.MAX_VALUE ? ans : -1;
}
}
注意一个小细节, 你看当他的for循环执行成功之后, 也就是找到一个合理的gap之后, 后面不是立刻return, 而是将window向右移动, 然后继续搜索; 因为我们现在分析的是flower bed, 而不是时间轴, 所以第一个找到的不是first day, 所以我们要把整个flowerbed都走完, 才能知道时间上最小的是多少;
总体来说这个算法是一个需要相当深刻的观察才能想到的;
That means whenever whether some interval can be a candidate and it fails first at i, indices j < i can't be the start of a candidate interval. This motivates a sliding window approach.
这个讲的很轻巧了; sliding window本身并不是这个motivation; 这里的这个motivation, 实际上更像是KMP的那种分析方式: 避免backup;
我认为editorial2是需要重点掌握的, 介绍了一个经典的题型, 在思路上面比较容易拓展和有学习度; 第一个算法实在是有点投机取巧, 第三个方法难度比较高: 能够看出来KMP结构, 这个在面试当中是相当的困难的;
https://leetcode.com/problems/k-empty-slots/discuss/107931/JavaC++-Simple-O(n)-solution
It seems that this question has some mistakes. I think there are two places that might lead to misunderstandings: (please feel free to tell me if I’m incorrect)
- flowers[i] = x should mean that the unique flower that blooms at day i+1 (not i) will be at position x.
- If you can get multiple possible results, then you need to return the minimum one.
The idea is to use an array days[] to record each position’s flower’s blooming day. That means days[i] is the blooming day of the flower in position i+1. We just need to find a subarray days[left, left+1,..., left+k-1, right] which satisfies: for any i = left+1,..., left+k-1, we can have days[left] < days[i] && days[right] < days[i]. Then, the result is max(days[left], days[right]).
Java version:
public int kEmptySlots(int[] flowers, int k) {
int[] days = new int[flowers.length];
for(int i=0; i<flowers.length; i++)days[flowers[i] - 1] = i + 1;
int left = 0, right = k + 1, res = Integer.MAX_VALUE;
for(int i = 0; right < days.length; i++){
if(days[i] < days[left] || days[i] <= days[right]){
if(i == right)res = Math.min(res, Math.max(days[left], days[right])); //we get a valid subarray
left = i;
right = k + 1 + i;
}
}
return (res == Integer.MAX_VALUE)?-1:res;
}
C++ version:
int kEmptySlots(vector<int>& flowers, int k) {
vector<int> days(flowers.size());
for(int i=0; i<flowers.size();i++)days[flowers[i] - 1] = i + 1;
int left = 0, right = k + 1, res = INT_MAX;
for(int i = 0; right < days.size(); i++){
if(days[i] < days[left] || days[i] <= days[right]){
if(i == right)res = min(res, max(days[left], days[right])); //we get a valid subarray
left = i, right = k + 1 + i;
}
}
return (res == INT_MAX)?-1:res;
}
这个就是editorial3的第一作者了, 这个想法本身还是相当厉害的;
另外注意他这个代码比awice那个代码还要简洁: 他这个for循环实际上是两个循环合并到了一起; 他注意到, 当我们要advance一个window的时候, 实际上总是让新window的开头放在i(只不过如果你之前的window搜索成功的话, 那么这个时候i是等于right的), 所以他把这两种情况合并到一起来写了; 这个就更加炫技了; awice那个写法实际上是更加好理解一些的;
A really instructive sliding window solution. Just change several lines to make it more readable.
public int kEmptySlots(int[] flowers, int k) {
int[] days = new int[flowers.length];
for (int i = 0; i < days.length; i++) {
days[flowers[i] - 1] = i + 1;
}
int left = 0;
int right = k + 1;
int res = Integer.MAX_VALUE;
for (int i = 1; right < days.length; i++) {
// current days[i] is valid, continue scanning
if (days[i] > days[left] && days[i] > days[right]) {
continue;
}
// reach boundary of sliding window, since previous number are all valid, record result
if (i == right) {
res = Math.min(res, Math.max(days[left],days[right]));
}
// not valid, move the sliding window
left = i;
right = left + k + 1;
}
return res == Integer.MAX_VALUE ? -1 : res;
}
看这个人的最后一个comment, 他这里就是没有get到OP炫技的部分: 最后的这个left和right的移动, 实际上是涵盖了success和fail两种情况的;
@huajiaaaa There are two cases that we need to update left and right: 1. i arrives the position right (it means that we get a vliad subarray); 2. we find days[i] < days[left] || days[i] < days[right] (it means that the pre-assumed subarray is not correct).
这个人才是理解了; 哦不对, 这个是OP自己的发言;
https://leetcode.com/problems/k-empty-slots/discuss/107942/Java-Accepted-Solution
public int kEmptySlots(int[] flowers, int k) {
TreeSet<Integer> treeSet = new TreeSet<>();
for (int i = 0; i < flowers.length; i++) {
int current = flowers[i];
Integer next = treeSet.higher(current);
if (next != null && next - current == k + 1) {
return i + 1;
}
Integer pre = treeSet.lower(current);
if (pre != null && current - pre == k + 1) {
return i + 1;
}
treeSet.add(current);
}
return -1;
}
不讲道理的treeset解法;
底下有人给出解释:
Okay, I will add explain myself.
First understand the representation of array(non zero indexed)
[1,3,2] means on, day 1, flower will bloom at index 1.
On day 2, flower will bloom at index 3.
On day 3, flower will bloom at index 2.
So basically this array holds days as index, and value as position the flower will bloom.
This representation will make the problem simpler to understand now.
So now consider example - [4,1,3,5,2].
Day 1 : [0,0,0,B,0] - flower at index 4 bloom : setContains : [4]
Day 2 : [B,0,0,B,0] - flower at index 1 bloom : setContains : [1,4] : k = 2
Day 3 : [B,0,B,B,0] - flower at index 3 bloom : setContains : [1,3,4] : k = 1, k = 0
Day 4 : [B,0,B,B,B] - flower at index 5 bloom : setContains : [1,3,4,5] : k = 0
Day 5 : [B,B,B,B,B] - flower at index 2 bloom : setContains : [1,2,3,4,5] : k = 0
On day 2, when you add 1, set has [1,4]. This means that there are no flowers that bloom in between these two positions. (which is 2,3). So two flowers.(k=2)
On day 3, when you add 3, set has [1,3,4]. This means that there are no flowers that bloom in between 1-3, and 3-4. (k = 1, and k = 0)
Similarly on day 4, when you add 5, position to left is 4. So k = 0. and so on.
So every day when a flower blooms, we just need to find out it’s left and right bloomed flowers. All the flowers in between is guaranteed to be no-bloom.
Definition of set.higher : Returns the least element in this set strictly greater than the given element, or null if there is no such element.
Definition of set.lower : Returns the greatest element in this set strictly less than the given element, or null if there is no such element
没有仔细看了, 因为这个方法一用, 实际上整个问题就太简单了;
https://leetcode.com/problems/k-empty-slots/discuss/107960/C++-ordered-set-Easy-solution
class Solution {
public:
int kEmptySlots(vector<int>& flowers, int k) {
set<int> bloom;
for (int i = 0; i < flowers.size(); i++) {
int p = flowers[i];
auto it = bloom.insert(p).first;
if (it != bloom.begin()) {
if (p-*(--it) == k+1) return i+1;
it++;
}
if (++it != bloom.end() && *it-p == k+1) return i+1;
}
return -1;
}
};
c++的写法, 好像应该是差不多的; 没有仔细看了, 好像返回的这个begin, ++之后什么的自动就是next了;
c++的库特别的丰富, 所以什么写法的人都有;
@zestypanda thanks for sharing your solution! I used the same concept to write the solution below. I found set::equal_range() works well here, since the second iterator already points to the neighbor to the right, and only the first iterator needs to be modified ( decrement by one ) for reaching the neighbor to the left.
Summary: one day at time, insert the day’s blooming flower into a set blooms, then check the inserted flower’s neighbor to the left and right to see if they are delta ( k+1 ) positions-away from eachother. If so, return the current day ( i + 1 ).
class Solution {
public:
int kEmptySlots(vector<int>& flowers, int k) {
int delta=k+1;
set<int> blooms{};
for (int i=0; i<flowers.size(); ++i){
int day=i+1, position=flowers[i];
blooms.insert(position);
auto neighbor=blooms.equal_range(position);
if (neighbor.first!=blooms.begin()){
int left=*(--neighbor.first);
if (position-left==delta){ return day; }
}
if (neighbor.second!=blooms.end()){
int right=*(neighbor.second);
if (right-position==delta){ return day; }
}
}
return -1;
}
};
好像是差不多的;
submission: 15(98):
class Solution {
public int kEmptySlots(int[] flowers, int k) {
int bucketSize = k + 1;
int bucketCount = flowers.length / bucketSize + 1;
int[] bucketMax = new int[bucketCount];
for (int i = 0; i < bucketCount; i++) bucketMax[i] = Integer.MIN_VALUE;
int[] bucketMin = new int[bucketCount];
for (int i = 0; i < bucketCount; i++) bucketMin[i] = Integer.MAX_VALUE;
for (int i = 0; i < flowers.length; i++) {
int flower = flowers[i];
int bucket = (flower - 1)/bucketSize;
if (flower < bucketMin[bucket]) {
bucketMin[bucket] = flower;
if (bucket > 0 && bucketMax[bucket - 1] == flower - k - 1) {
return i + 1;
}
}
if (flower > bucketMax[bucket]) {
bucketMax[bucket] = flower;
if (bucket < bucketCount - 1 && bucketMin[bucket + 1] == flower + k + 1) {
return i + 1;
}
}
}
return -1;
}
}
不浪费时间, 先把trace全都打印出来; 我认为这个不代表画trace的能力不强, 毕竟现在是在理解别人的算法, 而不是写自己的算法, 所以中间这个学习成本, 能减少还是减少, 现在没有这个时间;
Your input
[6,5,8,9,7,1,10,2,3,4]
2
Your stdout
size: (3), count(4)
i:(0), flower:(6), bucket:(1)
[[null, 6, null, null],
[null, 6, null, null]]
i:(1), flower:(5), bucket:(1)
[[null, 5, null, null],
[null, 6, null, null]]
i:(2), flower:(8), bucket:(2)
[[null, 5, 8, null],
[null, 6, 8, null]]
i:(3), flower:(9), bucket:(2)
[[null, 5, 8, null],
[null, 6, 9, null]]
i:(4), flower:(7), bucket:(2)
[[null, 5, 7, null],
[null, 6, 9, null]]
i:(5), flower:(1), bucket:(0)
[[1, 5, 7, null],
[1, 6, 9, null]]
i:(6), flower:(10), bucket:(3)
[[1, 5, 7, 10],
[1, 6, 9, 10]]
首先注意他一个小操作: 他丢到buckets里面的这些flower本身还是1based的, 但是当他计算bucket的时候, 他先-1变成了0based, 这个体现了一个很好的素养, 因为以前也讲过, division, mod这些, 0based的时候出来的结果更加好理解和整合的多;
然后这个算法的思想也是很聪明的:
把整个bed分成好几个分块, 然后按照时间轴的顺序, 一点一点的填分块; 当新加入的这个flower是当前分块的最大值或者最小值的时候, 先更新最大值最小值, 然后要跟前后的两个bucket的对应最值进行比较, 如果长度满足要求(是K+2), 那么就成功;
这个做法的一个核心的技巧在于: bucket的size选择在K+1, 这样我们永远不用比较internal to one bucket, 因为不够大; 我们只需要比较inter bucket的数字之间的距离; 这个算法的设计真的是相当的高层面了;
这个做法看起来思路有点像UF, 但是实际上就算是看了这个算法之后我重新思考UF, 我认为这个题目用UF还是不好做;
Problem 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 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].
Difficulty:Hard
Total Accepted:12K
Total Submissions:34.4K
Contributor:今が最高
Companies
google
Related Topics
arraybinary search tree