2962.统计最大元素出现至少 K 次的子数组:滑动窗口

【LetMeFly】2962.统计最大元素出现至少 K 次的子数组:滑动窗口

力扣题目链接:https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times/

给你一个整数数组 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

解题方法:滑动窗口

首先遍历一遍数组得到数组中最大的元素。

之后使用两个指针分别指向窗口中的第一个和最后一个元素的下标,不断右移右指针,并将新元素加入窗口。

当窗口中“最大数个数”等于k时,不断右移左窗口并将左边元素移出窗口。此时左指针左边(不含左指针)的任何一个元素开始到右指针所组成的子数组都合法。

  • 时间复杂度$O(len(nums))$
  • 空间复杂度$O(1)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
* @Author: LetMeFly
* @Date: 2025-04-29 13:19:27
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-04-29 21:19:24
*/
typedef long long ll;

class Solution {
public:
long long countSubarrays(vector<int>& nums, int k) {
int mx = nums[0];
for (int t : nums) {
mx = max(mx, t);
}
ll ans = 0;
for (int l = 0, r = 0, cnt = 0; r < nums.size(); r++) {
cnt += nums[r] == mx;
while (cnt == k) {
cnt -= nums[l++] == mx;
}
ans += l;
}
return ans;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
'''
Author: LetMeFly
Date: 2025-04-29 13:19:47
LastEditors: LetMeFly.xyz
LastEditTime: 2025-04-29 21:21:03
'''
from typing import List

class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
mx = max(nums)
l = cnt = ans = 0
for t in nums:
cnt += t == mx
while cnt == k:
cnt -= nums[l] == mx
l += 1
ans += l
return ans

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
* @Author: LetMeFly
* @Date: 2025-04-29 13:19:49
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-04-29 21:23:01
*/
class Solution {
public long countSubarrays(int[] nums, int k) {
int mx = nums[0];
for (int t : nums) {
mx = Math.max(mx, t);
}
long ans = 0;
for (int l = 0, cnt = 0, r = 0; r < nums.length; r++) {
if (nums[r] == mx) {
cnt++;
}
while (cnt == k) {
if (nums[l++] == mx) {
cnt--;
}
}
ans += l;
}
return ans;
}
}

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
* @Author: LetMeFly
* @Date: 2025-04-29 13:20:02
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-04-29 13:23:23
*/
package main

func countSubarrays(nums []int, k int) (ans int64) {
M := nums[0]
for _, t := range nums {
M = max(M, t)
}
for l, r, cnt := 0, 0, 0; r < len(nums); r++ {
if nums[r] == M {
cnt++
}
for cnt >= k {
if nums[l] == M {
cnt -= 1
}
l++
}
ans += int64(l)
}
return
}

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

千篇源码题解已开源


2962.统计最大元素出现至少 K 次的子数组:滑动窗口
https://blog.letmefly.xyz/2025/04/29/LeetCode 2962.统计最大元素出现至少K次的子数组/
作者
发布于
2025年4月29日
许可协议