题目

类型：数组

解题思路

1、题目中的time，意思其实是判定界限。
2、答案落在 [time, n - time) 范围内
3、规定了「适合打劫银行的日子」左右侧需要满足「非递增」和「非递减」的性质。

解题关键：
1、令 n 为 security数组长度
2、预处理 g 数组，g[i] 代表当前时间 security[i] 与前一时间 security[i - 1] 的大小关系，当 security[i] > security[i - 1] 时有 g[i] = 1 ，当 security[i] < security[i - 1] 时有 g[i] = -1 ，否则 g[i] = 0（边界情况）
3、对 g 应用「前缀和」思想：使用 a 数组记录前缀 1 的数量，使用 b 数组记录前缀 −1 的数量。

最终，如果 i 为「适合打劫银行的日子」，那么满足 time <= i < n - time ，且满足 (i - time, i] 范围前缀 1 数量为 0，(i, i + time] 范围前缀 -1 数量为 0。

代码

class Solution {
    public List<Integer> goodDaysToRobBank(int[] security, int time) {
        int n = security.length;
        int[] g = new int[n];
        for (int i = 1; i < n; i++) {
            if (security[i] == security[i - 1]) continue;
            g[i] = security[i] > security[i - 1] ? 1 : -1;
        }
        int[] a = new int[n + 1], b = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = a[i - 1] + (g[i - 1] == 1 ? 1 : 0);
        for (int i = 1; i <= n; i++) b[i] = b[i - 1] + (g[i - 1] == -1 ? 1 : 0);
        List<Integer> ans = new ArrayList<>();
        for (int i = time; i < n - time; i++) {
            int c1 = a[i + 1] - a[i + 1 - time], c2 = b[i + 1 + time] - b[i + 1];
            if (c1 == 0 && c2 == 0) ans.add(i);
        }
        return ans;
    }
}