适合打劫银行的日子 java

题目描述要求思路

动态规划

你和一群强盗准备打劫银行。给你一个下标从 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开始)。返回的日子可以任意顺序排列。 思路 动态规划

首先要确定好要输出的数字的范围使用一个数组存储第i天之前的天数，该天数不增加，使用另一个数组存储第i天之后的天数，该天数不减少其实如果满足左边的一个约束条件下一项就加1，全部满足条件的时候显然得到的这一项要比time大，右边亦然

class Solution {
    public List goodDaysToRobBank(int[] security, int time) {
         // 储存警卫数目的数组
        int n = security.length;
        // 适合打劫的日子的左边，记一个数组
        int[] left = new int[n];
       // 适合打劫的日子的右边，记一个数组
        int[] right = new int[n];
        for (int i = 1; i < n; i++) {
        // 判断一下约束条件
        left[i]=security[i] <= security[i -1]？left[i - 1] + 1:0;
        right[n - i - 1]=security[n - i - 1] <= security[n - i]? right[n - i] + 1:0;
        }
        // 储存一下返回结果
        List ans = new ArrayList<>();
        // 最后判断一下结果
        for (int i = time; i < n - time; i++) {
            if (left[i] >= time && right[i] >= time) {
        // 如果成立就储存一下结果
                ans.add(i);    
            }
        }
        return ans;
    }
}