【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 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 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 package mainfunc 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 和我的个人博客 ,原创不易,转载经作者同意后请附上原文链接 哦~
千篇源码题解已开源