点击获取AI摘要

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

给你一个整数数组 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 <= 10510^5
  • 1 <= nums[i] <= 10610^6
  • 1 <= k <= 10510^5

问题分析

给定一个长度为 n 的整数数组 nums 和正整数 k，我们需要统计满足“子数组中数组 nums 的最大元素至少出现 k 次”的所有连续子数组的个数。

  • 全局最大值：数组中所有元素的最大值，记作 M = max(nums)。
  • 子数组：数组中任意一段连续的元素序列。
  • 目标：统计所有子数组中，元素 M 出现次数 ≥ k 的子数组个数。

直接枚举所有子数组会有 O(n2)O(n^2) 个，无法在 n ≤ 10510^5 的规模下通过。因此，需要一个 O(n)O(n) 或 O(nlog⁡n)O(n \log n) 的方法。

算法思路

  1. 全局最大值定位：首先在数组 nums 中找到最大的元素 M = max(nums)。
  2. 子数组计数思路：我们要统计所有包含元素 M 至少出现 k 次的连续子数组。
  3. 滑动窗口＋双指针：统计“包含 M 出现次数 < k 的子数组数目”，记为 cnt_less。
    • 用双指针 left, right 扩展窗口，维护窗口中 M 的出现次数 count_M。
    • 每次将 right 向右移动，若 nums[right] == M 则 count_M += 1。
    • 当 count_M >= k 时，窗口不再满足“<k”条件，需要移动 left 且在移动时相应地更新 count_M，直到 count_M < k。
    • 对于每一个 right，当前满足 < k 的最长窗口长度是 right - left + 1，将其累加到 cnt_less。
  4. 总子数组数目：total=n(n+1)2.\text {total}= \frac{n(n+1)}2\text.
  5. 答案：answer=total−cnt_less\text{answer} = \text{total} - \text{cnt\_less}，即所有子数组减去不满足条件的那些。

时间复杂度

时间复杂度：O(n)O(n)，left 和 right 指针各最多移动 nn 次。

空间复杂度：O(1)O(1)，只使用常数级的额外变量。

代码分解

  1. 找最大值 ：M = max(nums)

  2. 初始化

    1
    2
    3
    4
    n = len(nums)
    left = 0
    count_M = 0
    cnt_less = 0

  3. 滑动窗口循环

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for right in range(n):
        if nums[right] == M:
            count_M += 1
        # 收缩左端，直到 count_M < k
        while count_M >= k:
            if nums[left] == M:
                count_M -= 1
            left += 1
        # 累加以 right 结尾的不满足子数组数
        cnt_less += (right - left + 1)

  4. 计算并返回结果

    1
    2
    total = n * (n + 1) // 2
    return total - cnt_less

代码实现

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
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # 1. 找到全局最大值 M
        M = max(nums)
        # 2. 统计出现次数 < k 的子数组数（滑动窗口）
        left = 0
        count_M = 0   # 窗口中 M 的出现次数
        cnt_less = 0  # 子数组中 M 出现次数 < k 的数量
        # 3. 滑动窗口遍历所有可能的右端点
        for right in range(n):
            # 扩张窗口：若新加入元素是 M，则计数器 +1
            if nums[right] == M:
                count_M += 1
            # 当窗口中 M 出现次数 >= k 时，收缩 left
            while count_M >= k:
                if nums[left] == M:
                    count_M -= 1
                left += 1
            # 此时窗口 [left..right] 都是 < k，子数组数量 = 窗口长度
            # 以 right 结尾的所有子数组的起点可以是 left, left+1, …, right
            cnt_less += (right - left + 1)
        # 4. 计算总子数组数并取差
        total = n * (n + 1) // 2
        return total - cnt_less

  • 输入：nums = [1,3,2,3,3], k = 2

    • 全局最大值 M = 3
    • 统计 <2 次的子数组数 cnt_less = 15 - 6 = 9 （总子数组 15 个，满足条件 6 个）
    • 返回 15 - 9 = 6，与题目示例一致。

  • 输入：nums = [1,4,2,1], k = 3

    • M = 4，在任何子数组中最多出现 1 次，均 <3
    • cnt_less = total = 10，所以返回 10 - 10 = 0。