[LeetCode]K Empty Slots

题目链接

这道题普通的做法就是按照天数来开花，每开一次花我们check左右相邻有没有满足条件的即可。我们可以把index存在bst中，这样每一次插入新的位置的时候，我们查看左右相邻的存在map中的index是不是满足相距k。如果存在的话，直接返回即可，因为我们是按照天数从小到大扫的。时间复杂度O(n * log n)，代码如下：


此外我们还有O(n)的方法，我们把输入array转化成days数组，其中days[i]代表坐标为i的话在第days[i]天开。这样我们从左向右扫的话，维护一个长度为k + 1的window，左右分别为left 和right：

• 如果在我们扫到i的时候发现到i == right，俺么说明我们找到了一个满足条件的结果，更新最小天数
• 如果days[i] < days[left] || days[i] < days[right]，说明这个window已经不合法了，并且所有i左边的开始window也不合法，因为i是这个window里第一个遇到的小于left或者right的天数，所以我们直接更新window， left = i， right = i + k + 1

时间复杂度O(n)，代码如下：