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

简介: 每日一题 --- 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
}


相关文章
|
6月前
|
Go C++
【力扣】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)
【2月更文挑战第18天】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)
59 6
|
6月前
|
Go C++
【力扣】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)
【2月更文挑战第17天】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)
44 8
每日一题 --- 942. 增减字符串匹配[力扣][Go]
每日一题 --- 942. 增减字符串匹配[力扣][Go]
每日一题 --- 942. 增减字符串匹配[力扣][Go]
|
算法 Go
每日一题 --- 442. 数组中重复的数据[力扣][Go]
每日一题 --- 442. 数组中重复的数据[力扣][Go]
每日一题 --- 442. 数组中重复的数据[力扣][Go]
每日一题 --- 933. 最近的请求次数[力扣][Go]
每日一题 --- 933. 最近的请求次数[力扣][Go]
每日一题 --- 933. 最近的请求次数[力扣][Go]
每日一题 --- 713. 乘积小于 K 的子数组[力扣][Go]
每日一题 --- 713. 乘积小于 K 的子数组[力扣][Go]
每日一题 --- 713. 乘积小于 K 的子数组[力扣][Go]
每日一题 --- 606. 根据二叉树创建字符串[力扣][Go]
每日一题 --- 606. 根据二叉树创建字符串[力扣][Go]
每日一题 --- 606. 根据二叉树创建字符串[力扣][Go]
|
Go 索引
每日一题 ---- 599. 两个列表的最小索引总和[力扣][Go]
每日一题 ---- 599. 两个列表的最小索引总和[力扣][Go]
每日一题 ---- 599. 两个列表的最小索引总和[力扣][Go]
|
存储 测试技术 Go
每日一题 --- 393. UTF-8 编码验证[力扣][Go]
每日一题 --- 393. UTF-8 编码验证[力扣][Go]
每日一题 --- 393. UTF-8 编码验证[力扣][Go]
每日一题 --- 590. N 叉树的后序遍历[力扣][Go]
每日一题 --- 590. N 叉树的后序遍历[力扣][Go]
每日一题 --- 590. N 叉树的后序遍历[力扣][Go]