Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

【刷题日记】2100. 适合打劫银行的日子

本次刷题日记的第 2 篇，力扣题为：2100. 适合打劫银行的日子 ，中等

一、题目描述：

示例如下：

二、思路分析：

1、这道题考察了什么思想？你的思路是什么？

看了这题的描述和示例，我们应该得到了如下几个信息

如果 time 等于 0 ，那么每一天都可以打劫银行，那么结果就是给出数组的所有下标
如果 time 比整个数组都大，结果一定是一个空数组，哪一天都不适合打劫
根据我们选择打劫的时间，需要满足这个条件： security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time]

根据条件，我们知道，无论选择哪一天打劫，需要满足，当天前需要有 time 天，且当天后也要有 time 天，同时，前后的 time 天还要满足数据的要求，我们数组长度需要满足这个条件才有的玩：2 * time + 1 小于等于数组的长度

以 [ 5, 3, 3, 3, 5, 6, 2 ] ，time = 2 为例

当我们选中某一个是否可以打劫的时候，当天的前 time 天和当天的后 time 天在数组上对应的数据是向当天的数据，逐渐变小的

那这样做起来就不难理解的，我们是否感觉和上一篇分享的刷题有点类似，我们是否也可以看成是转换成特殊的子数组的方式来处理，例如这样

咱们只需要找到满足前 time 天和后 time 天对应的区间，然后校验区间是否满足题目中的要求：打劫当天的前 time 天，数字递减（可以相等），打劫当天的后 time 天，数字递增（可以相等）

2、尝试编码

那么，根据上述的图示和逻辑，那么咱们不难写出类似于这样的代码

看样子感觉也没啥问题，那么咱们提交吧

提交后发现，给我们报了一个 超出时间限制

查看具体错误情况的时候，我们可以看到跑通了 128 个用例，但是对于一些数据量比较大的时候，上述的这种编码方式就不满足本题的要求了

那么，一定是有优化的空间，肯定是哪里处理的低效了

3、思考和探索

来我们一起来探索一下，同样还是以 [ 5, 3, 3, 3, 5, 6, 2 ] ，time = 2 为例

选择第一个区间的时候，打劫日是在下标为 2 的位置上，数字是 3，那么需要循环的的去判断打劫日和前 2 个数字，是否递减，同理，循环判断打劫日和后 2 个数字是否是递增，如果是，那么我们就得到一个打劫日

那么继续往下推进

当推进到下一个区间的时候，如果我们还是使用上述的方式，使用循环的方式来校验是否递增或者递减的话，那就会出现上面编码的结果**，对于数据量大的时候，时间超出限制**

实际上，对于上一个区间，我们已经明确知道打劫日的前后数据递增或者递减关系，那么区间往后走的时候，我们指定的新的打劫日

只需要和上一个打劫日比较，当前打劫日上的数据，是否小于上一个打劫日上的数据，且再判断当前区间的最右边的值，是否大于上一个打劫日区间的最右边值 即可

做一个这样的优化，那么对于多个打劫日挨在一起的区间时，我们就能大大降低循环的此时，大大减少时间复杂度

源码如下：

func goodDaysToRobBank(security []int, time int) []int {
	if time >= len(security) || 2*time+1 > len(security) {
		return []int{}
	}
	if time == 0 {
		res := []int{}
		for i, _ := range security {
			res = append(res, i)
		}
		return res
	}

	length := len(security)
	res := []int{}
	flag := true
	preloc := 0  // 上一次打劫日的下标
	preLastRight := 0  // 上一次打劫日所在区间最右边的数字下标
	for i := time; i <= length-1-time; i++ {
		if flag { // 判断需要使用 循环进行确认是否是打劫日
			if isOk(security, i, time) {
				res = append(res, i)
				flag = false
				preloc = i
				preLastRight = i + time
				continue
			}
		} else {
			if security[i] <= security[preloc] && security[i+time] >= security[preLastRight] { // 可以直接和上一个打劫日进行比较即可
				flag = false
				res = append(res, i)
				preloc = i
				preLastRight = i + time
			} else {
				flag = true
			}
		}
	}
	return res

}
// 判断是否是打劫日
func isOk(security []int, loc int, time int) bool {
	for i := loc - time; i < loc; i++ {
		if security[i] < security[i+1] {
			return false
		}
	}

	for i := loc + time; i > loc; i-- {
		if security[i] < security[i-1] {
			return false
		}
	}

	return true
}
复制代码