LeetCode 683. K 个空花盆（set/滑动窗口）
LeetCode 683. K 个空花盆（set/滑动窗口）
Michael阿明
发布于 2021-02-19 09:52:32
发布于 2021-02-19 09:52:32
文章被收录于专栏：Michael阿明学习之路
文章目录
1. 题目
花园里有 N 个花盆，每个花盆里都有一朵花。 这 N 朵花会在 N 天内依次开放，每天有且仅有一朵花会开放并且会一直盛开下去。
给定一个数组 flowers 包含从 1 到 N 的数字，每个数字表示在那一天开放的花所在的花盆编号。
例如， flowers[i] = x 表示在第 i+1 天盛开的花在第 x 个花盆中，i 和 x 都在 1 到 N 的范围内。
给你一个整数 k，请你输出在哪一天恰好有两朵盛开的花，他们中间间隔了 k 朵花并且都没有开放。
如果不存在，输出 -1。
样例 1:
输入:
flowers: [1,3,2]
k: 1
输出: 2
解释: 在第二天，第一朵和第三朵花都盛开了。
样例 2:
输入:
flowers: [1,2,3]
k: 1
输出: -1
注释 :
给定的数组范围是 [1, 20000]。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/k-empty-slots 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 set 有序
- 直接 set 插入开花的位置，返回 pair<iter, bool>
- 查看 iter 前后是否存在差距为 k+1 的元素
class Solution {
public:
int kEmptySlots(vector<int>& bulbs, int k) {
int i;
set<int> s;
s.insert(bulbs[0]);
for(i = 1; i < bulbs.size(); i++)
{
auto p = s.insert(bulbs[i]);
auto it = p.first, end = p.first;
if(p.first != s.begin())
{ //前面有元素
if(abs(*(--it)-bulbs[i])==k+1)
return i+1;
}
it = p.first, end = --s.end();
if(p.first != end)
{ //后面有元素
if(abs(*(++it)-bulbs[i])==k+1)
return i+1;
}
}
return -1;
}
};424 ms 84.6 MB
2.2 滑动窗口
- 参考题解
class Solution {
public:
int kEmptySlots(vector<int>& bulbs, int k) {
int i, l = 0, r = k+1, d = INT_MAX;
vector<int> day(bulbs.size());
for(i = 0; i < bulbs.size(); i++)
day[bulbs[i]-1] = i+1;
i = 1;
while(r < bulbs.size())
{
if(day[l] < day[i] && day[i] > day[r])
{
i++;//这天比端点都晚开花
continue;
}
if(i == r)
d = min(d, max(day[l], day[r]));//求最早的那天
//不满足，从i开启新的窗口
l = i;
r = i+k+1;
i++;
}
return d==INT_MAX ? -1 : d;
}
};328 ms 78.2 MB
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/07/16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
