LC 683. K Empty Slots 【lock,hard】
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].
Runtime: 128 ms, faster than 89.38% of C++ online submissions for K Empty Slots.
网上的解法。
class Solution {
public:
int kEmptySlots(vector<int>& flowers, int k) {
int n = flowers.size();
vector<int> days(n, );
for (int i = ; i < flowers.size(); i++) {
days[flowers[i] - ] = i + ;
}
int left = , right = k+, ret = INT_MAX;
for (int i = ; right < n; i++) {
if (days[i] < days[left] || days[i] <= days[right]) {
if (i == right) ret = min(ret, max(days[left], days[right]));
left = i;
right = i + k + ;
}
}
return ret == INT_MAX ? - : ret;
}
};
最新文章
- CSS初始化样式
- Base:-用数组赋值实现while和shift功能
- PHP 数据安全问题总结
- 前端手札--meta标记篇
- SDWebImage笔记
- 如何理解和熟练使用JS 中的call apply
- Redis初步
- 配置struts tags 输出HTML
- CSV文件规则
- 《JavaScript高级程序设计 第3版》-学习笔记-1
- scala学习笔记——特质
- hdu 4467 Graph
- 用 label 控制 Pod 的位置 - 每天5分钟玩转 Docker 容器技术(128)
- java三大版本和核心优势
- Nginx 负载均衡一致性算法
- python的高阶函数式编程
- 微信小程序之wx.request:fail错误,真机预览请求无效问题解决,安卓,ios网络预览异常
- UVA 12293 - Box Game(博弈)
- 前端开发---HTML---介绍
- Windows下查看端口常用命令以及关闭端口的方法