力扣每日一题2022-03-06中等题：适合打劫银行的日子

题目描述思路

动态规划

Python实现Java实现

适合打劫银行的日子

本题中要求的适合打劫的第i天需要满足：第i天前连续time天警卫数量都是非递增以及第i天后连续time天警卫数量都是非递减。所以只需要计算出第i天前警卫数量连续非递增的天数以及第i天后警卫数量连续非递减的天数，即可判断是否适合第i天打劫。设第i天前警卫数量连续非递增的天数为lefti，第i天后警卫数量连续非递减的天数为righti，当第i天同时满足lefti>time和righti

如果第i天的警卫数目小于等于第i-1天的警卫数目，假设已知第i天前有j天连续非递增，则此时有 s e c u r i t y ( i − 1 ) < = s e c u r i t y ( i − 2 ) < = . . . < = s e c u r i t y ( i − j − 1 ) security_(i-1) <= security_(i-2) <= ... <= security_(i-j-1) security(​i−1)<=security(​i−2)<=...<=security(​i−j−1)，又有 s e c u r i t y i < = s e c u r i t y ( i − 1 ) security_i <= security_(i-1) securityi​<=security(​i−1)，则 l e f t i = j + 1 = l e f t ( i − 1 ) + 1 left_i = j+1 = left_(i-1) + 1 lefti​=j+1=left(​i−1)+1；如果第i天的警卫数目大于第i-1天的警卫数目，则lefti=0。如果第i天的警卫数目小于等于第i+1天的警卫数目，假设已知第i+1天后有j天连续非递减，则满足 s e c u r i t y ( i + 1 ) < = s e c u r i t y ( i + 2 ) < = . . . < = s e c u r i t y ( i + j + 1 ) security_(i+1) <= security_(i+2) <= ... <= security_(i+j+1) security(​i+1)<=security(​i+2)<=...<=security(​i+j+1)，又有 s e c u r i t y i < = s e c u r i t y ( i + 1 ) security_i <= security_(i+1) securityi​<=security(​i+1)，则 r i g h t i = j + 1 = r i g h t ( i + 1 ) + 1 right_i = j+1 = right_(i+1)+1 righti​=j+1=right(​i+1)+1；如果第i天的警卫数目小于第i+1天的警卫数目，则righti=0。
依次检测所有日期，即可得到所有适合打劫的日子。 Python实现

class Solution:
    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:
        n = len(security)
        left = [0] * n
        right = [0] * n
        for i in range(1, n):
            if security[i] <= security[i-1]:
                left[i] = left[i-1] + 1
            if security[n-i-1] <= security[n-i]:
                right[n-i-1] = right[n-i] + 1
        return [i for i in range(time, n-time) if left[i] >= time and right[i] >= 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++) {
            if (security[i] <= security[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
            if (security[n - i - 1] <= security[n - i]) {
                right[n - i - 1] = right[n - i] + 1;
            }
        }

        List ans = new ArrayList<>();
        for (int i = time; i < n - time; i++) {
            if (left[i] >= time && right[i] >= time) {
                ans.add(i);    
            }
        }
        return ans;
    }
}