2100.适合打劫银行的日子

原题

一、直接法（超时）

对每个数i，遍历其左右time的范围[i-time, i+time]，复杂度O(n^2)

class Solution:
    def goodDaysToRobBank(self, s: List[int], time: int) -> List[int]:
        n = len(s)
        res = []
        for i in range(time, n-time):
            j= k = i
            flag = True
            while j > i-time and k < i + time :
                if s[j-1] >= s[j] and s[k+1]  >= s[k]:
                    j -= 1
                    k += 1
                else:
                    flag =False
                    break
            if flag:
                res.append(i)
        return res             

二、dp(前缀和思想)

第一个数组left[i]记录从security[i]开始，左边连续非递增的元素数目

第二个数组right[i]记录从security[i]开始，右边连续非递减的元素数目。只有符合leftD[i] >= time && rightD[i] >= time的security[i]才适合。

class Solution:
    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:
        n = len(security)
        left, right = [0]*n, [0]*n
        sign = 0    #用于标记连续递减的起始位置
        i = 0
        while i < n:
            if i == 0:
                left[i] = 0
            else:
                if security[i-1] < security[i]:     #递减关系从i开始断开，重新标记sign
                    sign = i
                left[i] = i-sign
            i +=1
        sign = n-1
        i = n-1
        while i >= 0:
            if i == n-1:
                right[i] = 0
            else:
                if security[i] > security[i+1]:
                    sign = i
                right[i] = sign-i
            i -= 1
        res = []
        for i in range(n):
            if left[i]>=time and right[i]>=time:
                res.append(i)
        return res