1. 题目描述
给你一个整数数组 nums 和一个 正整数 k 。
请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组,并返回满足这一条件的子数组的数目。
子数组是数组中的一个连续元素序列。
示例 1:
输入:nums = [1,3,2,3,3], k = 2
输出:6
解释:包含元素 3 至少 2 次的子数组为:[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3] 。
示例 2:
输入:nums = [1,4,2,1], k = 3
输出:0
解释:没有子数组包含元素 4 至少 3 次。
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 106
1 <= k <= 105
2. 分析
核心思路:滑动窗口
找到max元素
固定左端点,找到最小满足窗口。此时扩散右端点至末尾的所有子数组均满足。
3. 代码
func countSubarrays(nums []int, k int) int64 {
// 1. 先找到max
mx := max(nums...)
// 2. 左右指针滑窗,固定左端点,寻找满足的右端点
l, r := 0, 0
n := len(nums)
cnt := 0
ans := 0
for {
if r == n {
break
}
for r < n && cnt < k {
if nums[r] == mx {
cnt++
}
r++
}
if cnt < k {
break
}
for l < r && cnt >= k {
// 扩散右端点
ans += n - r + 1
if nums[l] == mx {
cnt--
}
l++
}
}
return int64(ans)
}
func max(nums ...int) int {
val := nums[0]
for _, v := range nums {
if val < v {
val = v
}
}
return val
}
评论