肥城市建设局网站,百科网站建设,广告制作材料价格单,做单网站文章目录1. 题目2. 解题2.1 set 有序2.2 滑动窗口1. 题目
花园里有 N 个花盆#xff0c;每个花盆里都有一朵花。 这 N 朵花会在 N 天内依次开放#xff0c;每天有且仅有一朵花会开放并且会一直盛开下去。
给定一个数组 flowers 包含从 1 到 N 的数字#xff0c;每个数字表…
文章目录1. 题目2. 解题2.1 set 有序2.2 滑动窗口1. 题目
花园里有 N 个花盆每个花盆里都有一朵花。 这 N 朵花会在 N 天内依次开放每天有且仅有一朵花会开放并且会一直盛开下去。
给定一个数组 flowers 包含从 1 到 N 的数字每个数字表示在那一天开放的花所在的花盆编号。
例如 flowers[i] x 表示在第 i1 天盛开的花在第 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 插入开花的位置返回 pairiter, bool查看 iter 前后是否存在差距为 k1 的元素
class Solution {
public:int kEmptySlots(vectorint bulbs, int k) {int i;setint 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])k1)return i1;}it p.first, end --s.end();if(p.first ! end){ //后面有元素if(abs(*(it)-bulbs[i])k1)return i1;}}return -1;}
};424 ms 84.6 MB
2.2 滑动窗口
参考题解
class Solution {
public:int kEmptySlots(vectorint bulbs, int k) {int i, l 0, r k1, d INT_MAX;vectorint day(bulbs.size());for(i 0; i bulbs.size(); i)day[bulbs[i]-1] i1;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 ik1;i;}return dINT_MAX ? -1 : d;}
};328 ms 78.2 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
