这道题目名字很有趣,本质上是寻找一段序列中的极值点。想到的生活中的应用,大概是买股票了:)
https://leetcode-cn.com/problems/find-good-days-to-rob-the-bank/

解题思路

  1. 顺序遍历security,使用一个数组non_inc保存当前下标i时,前置非递增的数目;
  2. 逆序遍历security,使用一个数nd表示当前下标i时,后置非递减的数目,若nd >= time && non_inc[i] >= time成立,则下标i加入答案数组result

还要注意处理time为零与len(security)为1的情况。

时间复杂度O(N),空间复杂度O(N)。

file

代码

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
}
最后修改日期: 2022年3月7日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。