Leetcode-​2962. 统计最大元素出现至少 K 次的子数组​

Problem: 2962. 统计最大元素出现至少 K 次的子数组

思路

滑动窗口

解题过程

• 确定最大值：首先找到数组中的最大值 max_value。

• 滑动窗口：使用滑动窗口技巧，统计每个以 r 结尾的子数组中，满足条件的起始位置数量。

• 计数逻辑：

右指针 r 扩展窗口，统计最大值出现的次数 cnt。

当 cnt >= k 时，收缩左指针 l 直到条件不再满足，此时所有起始位置 <= l 的子数组都满足条件，贡献 l+1 个有效子数组。

Code

python

class Solution:def countSubarrays(self, nums: List[int], k: int) -> int:max_v = max(nums)l = ans = 0cnt = 0for r, x in enumerate(nums):if x == max_v:cnt += 1while cnt >= k:if nums[l] == max_v:cnt -= 1l += 1ans += lreturn ans

c++

class Solution {
public:long long countSubarrays(vector<int>& nums, int k) {int max_value = *std::max_element(nums.begin(), nums.end());int l = 0;long long ans = 0;int cnt = 0;int n = nums.size();for(int r = 0; r < n; r ++){if(nums[r] == max_value) cnt ++;while(cnt >= k){if(nums[l] == max_value) cnt --;l ++;}ans += l;}return ans;}
};

复杂度

• 时间复杂度: O(n)

• 空间复杂度: O(1)