当前位置: 首页> 财经> 产业 > 网站百度云_手机代理服务器免费版_百度百家_seo排名分析

网站百度云_手机代理服务器免费版_百度百家_seo排名分析

时间:2025/7/11 0:15:06来源:https://blog.csdn.net/qq_29248103/article/details/147612444 浏览次数:0次
网站百度云_手机代理服务器免费版_百度百家_seo排名分析

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

在这里插入图片描述

问题分析

输入:一个整数数组 nums 和一个正整数 k。
目标:找到所有子数组,使得该子数组中的最大元素至少出现 k 次,并返回这样的子数组的数量。

思考

  1. 找到数组中的最大值
    首先,我们需要找到数组 nums 中的最大值 mx。
  2. 统计 mx 的出现次数
    然后,我们遍历数组,统计 mx 的出现次数 cnt_mx。
  3. 使用滑动窗口技术
    为了高效地找到所有满足条件的子数组,我们可以使用滑动窗口技术:
    初始化:设置两个指针 left 和 right,分别表示窗口的左边界和右边界。同时,初始化 cnt_mx(窗口内 mx 的出现次数)和 ans(满足条件的子数组数量)。
    扩展窗口:遍历数组,每次将 right 指针向右移动一位,如果当前元素等于 mx,则 cnt_mx 加 1。
    收缩窗口:当 cnt_mx 达到 k 时,进入内部 while 循环,移动 left 指针,缩小窗口,直到 cnt_mx 小于 k。在每次移动 left 指针时,如果 nums[left] 等于 mx,则 cnt_mx 减 1。
    更新答案:每次迭代时,ans 增加 left 的值,表示以 right 为右端点且长度不小于 left 的子数组都满足条件。

代码

class Solution:def countSubarrays(self, nums: List[int], k: int) -> int:mx = max(nums)ans = cnt_mx = left = 0for x in nums:if x == mx:cnt_mx += 1while cnt_mx == k:if nums[left] == mx:cnt_mx -= 1left += 1ans += leftreturn ans

复杂度分析

时间复杂度
遍历数组:外层 for 循环遍历数组,时间复杂度为 O(n)。
滑动窗口:内层 while 循环在最坏情况下每个元素最多被访问两次(一次由 right,一次由 left),因此时间复杂度也为 O(n)。
综合上述分析,总的时间复杂度为 O(n)。
空间复杂度
额外空间:只使用了常数级的额外空间(mx、ans、cnt_mx、left 等变量),因此空间复杂度为 O(1)。

学习

在这里插入图片描述

作者:灵茶山艾府
链接:https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times/solutions/2560940/hua-dong-chuang-kou-fu-ti-dan-pythonjava-xvwg/
来源:力扣(LeetCode)

关键字:网站百度云_手机代理服务器免费版_百度百家_seo排名分析

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: