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 <= 105
• 0 <= security[i], time <= 105

思路

方法一：分类讨论

时间复杂度$O(n)$，空间复杂度O(1)，难度※※

$time=0$的情况特殊考虑，每天都是“打劫日”。否则：

能够成为答案的一天，必定是 $前一天\geq这一天\leq下一天$

因此我们使用两个变量 $lianXuXiaDays$(表示非递增的天数)和$couldAsUp4Begin$(从此以后可以开始非递减的那一天)

也就是说，在连续$lianXuXiaDays$天的非递增后，若$lianXuXiaDays\geq time$，那么只要从今天起的连续$time$天都非递减，今天就“抢劫日”。

所以我们在$lianXuXiaDays\geq time$时，就可以将$couldAsUp4Begin$记为今天。

若之后的$time$天及以上都非递减，那么此时记录的$couldAsUp4Begin$就是一个“抢劫日”。

因此在向后的遍历中，如果仍然处于非递减状态，就可以判断是否有$couldAsUp4Begin$，如果有($\neq -1$)就判断今天距离$couldAsUp4Begin$是否$\geq time$天，如果$\geq time$，就说明$couldAsUp4Begin$后的连续$time$天都是非递减，因此$couldAsUp4Begin$就是一个抢劫日。

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

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的非递减，并且从那天起没有递增的一天 | Lable1
                    if (i - couldAsUp4Begin >= time) {  // 如果今天距离那天≥time，那天就是抢劫日
                        ans.push_back(couldAsUp4Begin);  // 先把抢劫日添加到答案中去
                        if (security[couldAsUp4Begin + 1] <= security[couldAsUp4Begin]) {  // 如果抢劫日的下一天仍然是非递增，那么下一天之前肯定有至少time天的非递增
                            couldAsUp4Begin++;  // 下一天也可以作为开始非递减的一天
                        }
                        else {  // 否则
                            couldAsUp4Begin = -1;  // 下一天＞这个抢劫日，说明下一天必不满足“前面有至少time天的非递增”
                        }
                    }
                }
                else {  // couldAsUp4Begin = -1
                    if (lianXuXiaDays >= time) {  // 连续非递增天数≥time
                        couldAsUp4Begin = i;  // 从今天起可以开始非递减了
                    }
                }
            }
            else {  // 今 > 昨
                lianXuXiaDays = 0;  // 连续非递减天数中断
                if (couldAsUp4Begin != -1) {  // 这个同理于上面的“Lable1”处
                    if (i - couldAsUp4Begin >= time) {
                        ans.push_back(couldAsUp4Begin);
                        if (security[couldAsUp4Begin + 1] <= security[couldAsUp4Begin]) {
                            couldAsUp4Begin++;
                        }
                        else {
                            couldAsUp4Begin = -1;
                        }
                    }
                }
            }
        }
        return ans;  // 返回答案即可
    }
};

方法二

时间复杂度$O(n)$，空间复杂度O(n)，难度※

这种方法比上一种方法更容易实现，但是空间复杂度比上种方法要高。

我们可以用$O(n)$的时间复杂度求出每一天的“之前的连续非递增天数”和“之后的连续非递减天数”

$xia[i]$表示第$i$天之前有几天非递增，$shang[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$ 和 $shang[i] \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;
    }
};

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/133324938