# 2100.适合打劫银行的日子

[原题](https://leetcode-cn.com/problems/find-good-days-to-rob-the-bank/)

## 一、直接法（超时）

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

```python
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]才适合。

```python
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
```