【刷题日记】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 }
通过上述编码，和注释，我们就不难看出，本次的编码比上面尝试的编码高效了许多，减少了许多无用的循环
当然这只是其中一种解法，感兴趣的朋友可以看看更好的解法，例如官方的这种，直接引入 2 个数组，一个记录当前下标左边的递减情况，一个记录右边的递增情况，如下图这样
四、总结：
本题的解法，空间复杂度是 O(n)，n 是对应数组的长度，官方的解法时间复杂为 O(n)，n 是对应数组的长度，感兴趣的可以一起刷起来
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
