题目:
你和一群强盗准备打劫银行。给你一个下标从 0 开始的整数数组 security ,其中 security[i] 是第 i 天执勤警卫的数量。日子从 0 开始编号。同时给你一个整数 time 。
如果第 i 天满足以下所有条件,我们称它为一个适合打劫银行的日子:
第 i 天前和后都分别至少有 time 天。
第 i 天前连续 time 天警卫数目都是非递增的。
第 i 天后连续 time 天警卫数目都是非递减的。
更正式的,第 i 天是一个合适打劫银行的日子当且仅当:security[i - time] >= security[i - time + 1] >= … >= security[i] <= … <= security[i + time - 1] <= security[i + time].
请你返回一个数组,包含 所有 适合打劫银行的日子(下标从 0 开始)。返回的日子可以 任意 顺序排列。
解题代码:
// 官方题解 func goodDaysToRobBank(security []int, time int) (ans []int) { n := len(security) // left 记录左侧连续非递增的个数 left := make([]int, n) // right 记录右侧连续非递减的个数 right := make([]int, n) for i := 1; i < n; i++ { if security[i] <= security[i-1] { left[i] = left[i-1] + 1 } if security[n-i-1] <= security[n-i] { right[n-i-1] = right[n-i] + 1 } } // 如果第i天,左边连续非递增和右边连续非递减的数都大于time // 则可以记录为适合打劫银行的日子 for i := time; i < n-time; i++ { if left[i] >= time && right[i] >= time { ans = append(ans, i) } } return }
我的思路,但是提交超时
// 超时 func goodDaysToRobBank(security []int, time int) []int { slen := len(security) if slen < 2*time + 1 { return nil } var ans []int if time == 0 { for i := 0; i < slen; i++ { ans = append(ans, i) } } else { for i := time; i < slen - time; i++ { if isIncreasingOrDecline(security[i-time:i + 1],1) && isIncreasingOrDecline(security[i:i+1+time], -1) { ans = append(ans, i) } } } return ans } func isIncreasingOrDecline(nums []int,n int) bool { if n > 0 { for j := 0; j < len(nums) - 1; j++ { if nums[j + 1] > nums[j] { return false } } } else { for j := 0; j < len(nums) - 1; j++ { if nums[j + 1] < nums[j] { return false } } } return true }