网站制作易捷网络,十大社区团购平台有哪些,网站开发前台后台,帮中介做网站赚钱吗【LetMeFly】2100.适合打劫银行的日子 现在力扣上好像改题面为2100. 适合野炊的日子了。 力扣题目链接#xff1a;https://leetcode.cn/problems/find-good-days-to-rob-the-bank/
你和一群强盗准备打劫银行。给你一个下标从 0 开始的整数数组 security #xff0c;其中 sec…【LetMeFly】2100.适合打劫银行的日子 现在力扣上好像改题面为2100. 适合野炊的日子了。 力扣题目链接https://leetcode.cn/problems/find-good-days-to-rob-the-bank/
你和一群强盗准备打劫银行。给你一个下标从 0 开始的整数数组 security 其中 security[i] 是第 i 天执勤警卫的数量。日子从 0 开始编号。同时给你一个整数 time 。
如果第 i 天满足以下所有条件我们称它为一个适合打劫银行的日子
第 i 天前和后都分别至少有 time 天。第 i 天前连续 time 天警卫数目都是非递增的。第 i 天后连续 time 天警卫数目都是非递减的。
更正式的第 i 天是一个合适打劫银行的日子当且仅当security[i - time] security[i - time 1] ... security[i] ... security[i time - 1] security[i time].
请你返回一个数组包含 所有 适合打劫银行的日子下标从 0 开始。返回的日子可以 任意 顺序排列。 示例 1
输入security [5,3,3,3,5,6,2], time 2
输出[2,3]
解释
第 2 天我们有 security[0] security[1] security[2] security[3] security[4] 。
第 3 天我们有 security[1] security[2] security[3] security[4] security[5] 。
没有其他日子符合这个条件所以日子 2 和 3 是适合打劫银行的日子。示例 2
输入security [1,1,1,1,1], time 0
输出[0,1,2,3,4]
解释
因为 time 等于 0 所以每一天都是适合打劫银行的日子所以返回每一天。示例 3
输入security [1,2,3,4,5,6], time 2
输出[]
解释
没有任何一天的前 2 天警卫数目是非递增的。
所以没有适合打劫银行的日子返回空数组。提示
1 security.length 1050 security[i], time 105
思路
方法一分类讨论
small时间复杂度 O ( n ) O(n) O(n)空间复杂度O(1)难度※※** /smtps://leetcode-cn.com/problems/find-good-days-to-rob-the-bank/solution/letmefly-fen-lei-tao-lun-on-o1-by-letmef-1jgw/](https://img-blog.csdnimg.cn/img_convert/ca4a6ec46181f3756420620dbe776075.jpeg) t i m e 0 time0 time0的情况特殊考虑 插入链接与图片
因此我们使用两个变量 l i a n X u X i a D a y s lianXuXiaDays lianXuXiaDays(表示非递增的天数)和 c o u l d A s U p 4 B e g i n couldAsUp4Begin couldAsUp4Begin(从此以后可以开始非递减的那一天)
也就是说在连续 l i a n X u X i a D a y s lianXuXiaDays lianXuXiaDays天的非递增后若 l i a n X u X i a D a y s ≥ t i m e lianXuXiaDays\geq time lianXuXiaDays≥time那么只要从今天起的连续 t i m e time time天都非递减今天就“抢劫日”。
所以我们在 l i a n X u X i a D a y s ≥ t i m e lianXuXiaDays\geq time lianXuXiaDays≥time时就可以将 c o u l d A s U p 4 B e g i n couldAsUp4Begin couldAsUp4Begin记为今天。
若之后的 t i m e time time天及以上都非递减那么此时记录的 c o u l d A s U p 4 B e g i n couldAsUp4Begin couldAsUp4Begin就是一个“抢劫日”。
因此在向后的遍历中如果仍然处于非递减状态就可以判断是否有 c o u l d A s U p 4 B e g i n couldAsUp4Begin couldAsUp4Begin如果有( ≠ − 1 \neq -1 −1)就判断今天距离 c o u l d A s U p 4 B e g i n couldAsUp4Begin couldAsUp4Begin是否 ≥ t i m e \geq time ≥time天如果 ≥ t i m e \geq time ≥time就说明 c o u l d A s U p 4 B e g i n couldAsUp4Begin couldAsUp4Begin后的连续 t i m e time time天都是非递减因此 c o u l d A s U p 4 B e g i n couldAsUp4Begin couldAsUp4Begin就是一个抢劫日。
更加详细的描述可参考注释
AC代码
C
class Solution {
public:vectorint goodDaysToRobBank(vectorint security, int time) {if (!time) { // time 0每天都是“打劫日”vectorint ans(security.size()); // 答案共有security.size()天for (int i 0; i security.size(); i) {ans[i] i; // 第i个答案是第i天}return ans;}vectorint ans;int lianXuXiaDays 0; // 连续↓或→的天数int couldAsUp4Begin -1; // 最早可以认为是开始连续上升的那一天 | 如果couldAsUp4Begina≠-1说明第a天之前至少有time天的非递增for (int i 1; i security.size(); i) { // 从第二天开始遍历if (security[i] security[i - 1]) { // ↓lianXuXiaDays; // 连续非递增天数if (lianXuXiaDays time) { // 如果连续非递增天数≥time那么今天之前就有≥time的非递减couldAsUp4Begin i; // 从今天开始可以非递减了}else { // 还没有连续非递增time天couldAsUp4Begin -1;}}else if (security[i] security[i - 1]) { // 今天和昨天相等也就是说既符合非递增又符合非递减lianXuXiaDays; // 符合非递增连续非递增天数if (couldAsUp4Begin ! -1) { // 前面有≥time的非递减并且从那天起没有递增的一天 | Lable1if (i - couldAsUp4Begin time) { // 如果今天距离那天≥time那天就是抢劫日ans.push_back(couldAsUp4Begin); // 先把抢劫日添加到答案中去if (security[couldAsUp4Begin 1] security[couldAsUp4Begin]) { // 如果抢劫日的下一天仍然是非递增那么下一天之前肯定有至少time天的非递增couldAsUp4Begin; // 下一天也可以作为开始非递减的一天}else { // 否则couldAsUp4Begin -1; // 下一天这个抢劫日说明下一天必不满足“前面有至少time天的非递增”}}}else { // couldAsUp4Begin -1if (lianXuXiaDays time) { // 连续非递增天数≥timecouldAsUp4Begin i; // 从今天起可以开始非递减了}}}else { // 今 昨lianXuXiaDays 0; // 连续非递减天数中断if (couldAsUp4Begin ! -1) { // 这个同理于上面的“Lable1”处if (i - couldAsUp4Begin time) {ans.push_back(couldAsUp4Begin);if (security[couldAsUp4Begin 1] securmai ty[coul AsUp4Begin]) { couldA Up4B gectin;}已完成 else {}couldA }}
Up4Begin -1;}}}}return ans; // 返回答案即可}
};方法二 时间复杂度 O ( n ) O(n) O(n)空间复杂度O(n)难度※
这种方法比上一种方法更容易实现但是空间复杂度比上种方法要高。
我们可以用 O ( n ) O(n) O(n)的时间复杂度求出每一天的“之前的连续非递增天数”和“之后的连续非递减天数” x i a [ i ] xia[i] xia[i]表示第 i i i天之前有几天非递增 s h a n g [ i ] shang[i] shang[i]表示第 i i i天之前有几天非递减
具体方法 从前向后遍历数组如果
今天≤昨天那么
xia[i] xia[i - 1] 1否则
xia[i] 0。初始值
xia[0] 0 从后向前遍历数组如果
今天≤昨天那么
shang[i] shang[i 1] 1否则
shang[i] 0。初始值
shang[security.size() - 1] 0
然后我们遍历每一天如果某天同时满足 x i a [ i ] ≥ t i m e xia[i]\geq time xia[i]≥time 和 s h a n g [ i ] ≥ t i m e shang[i] \geq time shang[i]≥time这天就是抢劫日。
AC代码
C
class Solution {
public:vectorint goodDaysToRobBank(vectorint security, int time) {vectorint xia(security.size());vectorint shang(security.size());xia[0] 0, shang[shang.size() - 1] 0;for (int i 1; i security.size(); i) {xia[i] security[i] security[i - 1] ? 0 : xia[i - 1] 1;}for (int i security.size() - 2; i 0; i--) {shang[i] security[i] security[i 1] ? 0 : shang[i 1] 1;}vectorint ans;for (int i 0; i security.size(); i) {if (xia[i] time shang[i] time)ans.push_back(i);}return ans;}
};同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/133324938
