LeetCode 2100.适合打劫银行的日子

【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 <= 10⁵
0 <= security[i], time <= 10⁵

思路

方法一：分类讨论

<small时间复杂度 $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 im e = 0$ 的情况特殊考虑插入链接与图片

因此我们使用两个变量 $l ian X u X ia D a ys$ (表示非递增的天数)和 $co u l d A s U p 4 B e g in$ (从此以后可以开始非递减的那一天)

也就是说，在连续 $l ian X u X ia D a ys$ 天的非递增后，若 $lianXuXiaDays\geq time$ ，那么只要从今天起的连续 $t im e$ 天都非递减，今天就“抢劫日”。

所以我们在 $lianXuXiaDays\geq time$ 时，就可以将 $co u l d A s U p 4 B e g in$ 记为今天。

若之后的 $t im e$ 天及以上都非递减，那么此时记录的 $co u l d A s U p 4 B e g in$ 就是一个“抢劫日”。

因此在向后的遍历中，如果仍然处于非递减状态，就可以判断是否有 $co u l d A s U p 4 B e g in$ ，如果有( $\neq -1$ )就判断今天距离 $co u l d A s U p 4 B e g in$ 是否 $\geq time$ 天，如果 $\geq time$ ，就说明 $co u l d A s U p 4 B e g in$ 后的连续 $t im e$ 天都是非递减，因此 $co u l d A s U p 4 B e g in$ 就是一个抢劫日。

更加详细的描述可参考注释

AC代码

C++

class Solution {
public:vector<int> goodDaysToRobBank(vector<int>& security, int time) {if (!time) {  // time = 0，每天都是“打劫日”vector<int> ans(security.size());  // 答案共有security.size()天for (int i = 0; i < security.size(); i++) {ans[i] = i;  // 第i个答案是第i天}return ans;}vector<int> ans;int lianXuXiaDays = 0;  // 连续↓或→的天数int couldAsUp4Begin = -1;  // 最早可以认为是开始连续上升的那一天 | 如果couldAsUp4Begin=a≠-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)$ 的时间复杂度求出每一天的“之前的连续非递增天数”和“之后的连续非递减天数”

$x ia [i]$ 表示第 $i$ 天之前有几天非递增， $s han g [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

然后我们遍历每一天，如果某天同时满足 $xia[i]\geq time$ 和 $\geq time$ ，这天就是抢劫日。

AC代码

C++

class Solution {
public:vector<int> goodDaysToRobBank(vector<int>& security, int time) {vector<int> xia(security.size());vector<int> 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;}vector<int> ans;for (int i = 0; i < security.size(); i++) {if (xia[i] >= time && shang[i] >= time)ans.push_back(i);}return ans;}
};