这道题目名字很有趣,本质上是寻找一段序列中的极值点。想到的生活中的应用,大概是买股票了:)
https://leetcode-cn.com/problems/find-good-days-to-rob-the-bank/
解题思路
- 顺序遍历
security
,使用一个数组non_inc
保存当前下标i
时,前置非递增的数目; - 逆序遍历
security
,使用一个数nd
表示当前下标i
时,后置非递减的数目,若nd >= time && non_inc[i] >= time
成立,则下标i加入答案数组result
。
还要注意处理time
为零与len(security)
为1的情况。
时间复杂度O(N),空间复杂度O(N)。
代码
func goodDaysToRobBank(security []int, time int) []int {
if time == 0{
result := make([]int, len(security), len(security))
for i:=0;i<len(result);i++{
result[i] = i
}
return result
}
if len(security) == 1{
if time>0{
return []int{}
}else{
return []int{0}
}
}
non_inc := make([]int, len(security), len(security))
result := make([]int, 0, 0)
ni := 0
nd := 0
for i:=1;i<len(security);i++{
if security[i]<=security[i-1]{
ni += 1
}else{
ni = 0
}
non_inc[i] = ni
}
if time == 0{
result = append(result, len(security)-1)
}
for i:=len(security)-2;i>=0;i--{
if security[i]<=security[i+1]{
nd += 1
}else{
nd = 0
}
if nd >= time && non_inc[i] >= time{
result = append(result, i)
}
}
return result
}
留言