6

力扣每日一题——适合打劫银行的日子

 2 years ago
source link: https://unique-pure.github.io/2022/03/06/suan-fa-xue-xi-ji-hua/mei-ri-yi-ti/20220306/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

1 题目描述

你和一群强盗准备打劫银行。给你一个下标从 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.length<=1051<=security.length<=105

0<=security[i],time<=1050<=security[i],time<=105

2 前缀和O(n)O(n)

我们需要找到的日子i满足[i-time, i + time]是一个山谷形状，如果直接暴力判断，显然不可行，复杂度为O(n2)O(n2)。

我们可以用g[i]来表示security[i]和security[i - 1]大小情况，这样，g数组则可以反映security的递增递减情况了，即如果第ii天前连续time天警卫数目都是非递增的，那么这time天的g[i]值不会为11；同理第ii天后连续time天警卫数目都是非递减的，那么这time天的g[i]值不会为−1−1。

所以我们可以利用前缀和快速求出g[i]的区间和，从而判断是否满足条件。

class Solution {
public:
    vector<int> goodDaysToRobBank(vector<int>& security, int time) {
        int len = security.size();
        vector<int> g(len), prefix1(len + 1), prefix2(len + 1), res;
        for (int i = 1; i < len; ++ i ) {
            if (security[i] == security[i - 1]) {
                g[i] = 0;
            } else if (security[i] > security[i - 1]) {
                g[i] = 1;
            } else {
                g[i] = -1;
            }
        }
        prefix1[0] = prefix2[0] = 0;
        for (int i = 1; i <= len; ++ i ) {
            prefix1[i] = prefix1[i - 1] + (g[i - 1] == 1 ? 1 : 0);
            prefix2[i] = prefix2[i - 1] + (g[i - 1] == -1 ? 1 : 0); 
        }
        for (int i = time; i < len - time; ++ i) {
            if (prefix1[i + 1] - prefix1[i + 1 - time] == 0 && prefix2[i + 1 + time] - prefix2[i + 1] == 0) {
                res.push_back(i);
            }
        }
        return res;
    }
};

3 双指针O(n)O(n)

可以先把某一天左侧满足连续递减的天数和右侧满足连续递增的天数记录下来，再通过一次遍历，找出满足要求的日子。

class Solution {
public:
    vector<int> goodDaysToRobBank(vector<int>& security, int time) {
        int len = security.size(), cnt = 0;
        vector<int> res, left(len), right(len);
        for (int i = 1; i < len; ++ i) {
            if (security[i] <= security[i - 1]) {
                ++ cnt;
            } else {
                cnt = 0;
            }
            left[i] = cnt;
        }
        cnt = 0;
        for (int i = len - 2; i >= 0; -- i) {
            if (security[i] <= security[i + 1]) {
                ++ cnt;
            } else {
                cnt = 0;
            }
            right[i] = cnt;
        }
        for (int i = time; i < len - time; ++ i) {
            if (left[i] >= time && right[i] >= time) {
                res.push_back(i);
            }
        }
        return res;
    }
};

4 滑动窗口O(n)O(n)

我们维持两个滑动窗口：

  • 记录前time天递增的天的个数（即不满足要求的天数）
  • 记录后time天递减的天的个数（即不满足要求的天数）

那么对于某一天来说，只有上述两个都为00才说明该天是可以打劫的。然后从左到右枚举每一天，更新窗口信息，找到符合要求的天即可。

class Solution {
public:
    vector<int> goodDaysToRobBank(vector<int>& security, int time) {
        int len = security.size(), cnt = 0;
        vector<int> res;
        if (2 * time + 1 > len) {
            return res;
        }
        if (time == 0) {
            for (int i = 0; i < len; ++ i ) {
                res.push_back(i);
            }
            return res;
        }
        int cnt1 = 0, cnt2 = 0; // 前面递增的人数和后面递减的人数
        for (int i = 1; i <= time; ++ i ) {
            if (security[i] > security[i - 1]) {
                ++ cnt1;
            }
        }
        for(int i = time + 1; i <= 2 * time; ++ i ) {
            if (security[i] < security[i - 1]) {
                ++ cnt2;
            }
        }
        for (int i = 0, j = 2 * time, p = time; ;  ) { // i为左窗口的左边界，j为右窗口的右边界
            if (!cnt1 && !cnt2) {
                res.push_back(p);
            }
            if (j + 1 == len) break;
            if (security[i] < security[i + 1]) -- cnt1;
            if (security[p] < security[p + 1]) ++ cnt1;
            if (security[p] > security[p + 1]) -- cnt2;
            if (security[j + 1] < security[j]) ++ cnt2;
            ++ i, ++ j, ++ p;
        }
        return res;
    }
};

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK