Solutions CS101

Appearance

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

sliding window, 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 <= 10^5
  • 1 <= nums[i] <= 10^6
  • 1 <= k <= 10^5

我们可以使用双指针的滑动窗口技巧解决问题：

  1. 找出整个数组中最大的元素 max_num。
  2. 使用两个指针 left 和 right 表示当前考察的子数组范围 [left, right]。
  3. 在移动 right 的过程中维护 max_num 出现的次数。
  4. 一旦某个窗口内 max_num 出现次数 ≥ k，就说明从 left 到 right 的所有以 right 结尾的子数组都满足条件（即从 left 到 right 的所有起点都可以构成有效子数组），可以计入答案。
  5. 此时我们尝试右移 left，继续寻找更小的有效窗口。

🧠 关键点

  • 时间复杂度要控制在 O(n)，因为 n 可达 1e5。
  • 我们只关心最大值出现的次数，其他数字可以忽略。

✅ Python 代码实现

python
from typing import List

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        max_num = max(nums)
        count = 0
        left = 0
        max_count = 0
        
        for right in range(len(nums)):
            if nums[right] == max_num:
                max_count += 1
            
            # 如果当前窗口中最大值出现次数 >= k
            while max_count >= k:
                # 那么从 left 到 right 结尾的所有子数组都满足条件
                # 所以一共有 (len(nums) - right) 个这样的子数组
                count += len(nums) - right
                if nums[left] == max_num:
                    max_count -= 1
                left += 1
                
        return count

复杂度分析

  • 时间复杂度：O(n)，每个元素最多被访问两次（一次由 right 进入窗口，一次由 left 移出窗口）
  • 空间复杂度：O(1)，仅使用几个变量保存状态