2100. 适合打劫银行的日子

mid

你和一群强盗准备打劫银行。给你一个下标从 0 开始的整数数组 security ，其中 security[i] 是第 i 天执勤警卫的数量。日子从 0 开始编号。同时给你一个整数 time 。

如果第 i 天满足以下所有条件，我们称它为一个适合打劫银行的日子：

第 i 天前和后都分别至少有 time 天。
第 i 天前连续 time 天警卫数目都是非递增的。
第 i 天后连续 time 天警卫数目都是非递减的。

请你返回一个数组，包含所有适合打劫银行的日子（下标从 0 开始）。返回的日子可以任意顺序排列。

示例 1：

1
2
输入：security = [5,3,3,3,5,6,2], time = 2
输出：[2,3]

示例 2：

1
2
输入：security = [1,1,1,1,1], time = 0
输出：[0,1,2,3,4]

示例 3：

1
2
输入：security = [1,2,3,4,5,6], time = 2
输出：[]

动态规划

把第 i 天前非递增天数和第 i 天非递减天数求出来就可以了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func goodDaysToRobBank(security []int, time int) []int {
	res := make([]int, 0)
	dp1 := make([]int, len(security))
	dp1[0] = 0
	for i := 1; i < len(security); i++ {
		if security[i-1] >= security[i] {
			dp1[i] = dp1[i-1] + 1
		} else {
			dp1[i] = 0
		}
	}
	dp2 := make([]int, len(security))
	dp2[len(security)] = 0
	for i := len(security) - 1; i >= 0; i-- {
		if security[i] <= security[i+1] {
			dp2[i] = dp2[i+1] + 1
		} else {
			dp2[i] = 0
		}
	}

	for i := time; i < len(security)-time; i++ {
		if dp1[i] >= time && dp2[i] >= time {
			res = append(res, i)
		}
	}
	return res
}

前两个 for 循环还能合到一起，不过懒得合了