【LeetCode笔记 - 每日一题】2100. 适合打劫银行的日子（Java、数组、前缀和）

0306 潮汕旅游回来啦，吃胖了，想学潮汕话（闽南语系）。恢复写题～

文章目录

• • 题目
  • 示例
  • 思路 & 代码

数组、前缀和

题目

输入数组，如果第 i 天满足以下所有条件，我们称它为一个适合打劫银行的日子：

• 第 i 天前和后都分别至少有 time 天。
• 第 i 天前连续 time 天警卫数目都是非递增的。
• 第 i 天后连续 time 天警卫数目都是非递减的。

请你返回一个数组，包含 所有 适合打劫银行的日子（下标从 0 开始）。返回的日子可以 任意 顺序排列。

示例

输入：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 是适合打劫银行的日子。

输入：security = [1,2,3,4,5,6], time = 2
输出：[]
解释：
没有任何一天的前 2 天警卫数目是非递增的。
所以没有适合打劫银行的日子，返回空数组。

思路 & 代码

1. 简单说就是求长度合适的V字子数组。线性遍历，空间换时间，对每一个位置，看前方符合非递增的最长子数组长度，用一个数组dec记录；看后方非递减最长，用inc记录。最后看哪些位置的前后长度都满足>time

class Solution {
    public List<Integer> goodDaysToRobBank(int[] se, int ti) {
        int n = se.length;
        List<Integer> res = new ArrayList<>();
        if (n < ti * 2 + 1) return res; // 长度不符合，提前结束
        int[] dec = new int[n], inc = new int[n];
        int cnt = 0; // 统计截止当前位置的连续情况
        for (int i = 1; i < n; i++) { // 前方
            if (se[i - 1] >= se[i]) ++cnt; // 满足就长度+1
            else cnt = 0; // 不满足就重新开始统计
            dec[i] = cnt;
        }
        cnt = 0; 
        for (int i = n - 2; i >= 0; i--) { // 后方
            if (se[i + 1] >= se[i]) ++cnt;
            else cnt = 0;
            inc[i] = cnt;
        }
        for (int i = 0; i < n; i++) { // 判断答案候选
            if (dec[i] >= ti && inc[i] >= ti) res.add(i);
        }
        return res;
    }
}

执行用时：5 ms, 在所有 Java 提交中击败了98.22%的用户

内存消耗：59.4 MB, 在所有 Java 提交中击败了11.15%的用户

通过测试用例：144 / 144

** 草稿的几个bug（所以说调试功能还是很有用的）**

• 答案要的是下标i
• 非递增/递减，注意不是严格增减。所以预处理数组、判断的时候是>=缺了等号就gg。

2. 大佬的解法

by 宫水三叶（每次点赞都排第一啊），说实话预处理我有点没懂。可能写完周赛脑子不够使了

来源：https://blog.csdn.net/weixin_55658749/article/details/123309042
本站部分图文来源于网络，如有侵权请联系删除。