每日一题 --- 2100. 适合打劫银行的日子[力扣][Go]-阿里云开发者社区

每日一题 --- 2100. 适合打劫银行的日子[力扣][Go]

2023-02-23 92

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 每日一题 --- 2100. 适合打劫银行的日子[力扣][Go]

题目：

你和一群强盗准备打劫银行。给你一个下标从 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
}