Medium

题目描述

给你一个整数数组 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

解题思路

解题思路

这道题要求统计子数组中最大元素出现至少 k 次的子数组数目。关键思路是使用滑动窗口算法。

核心观察：

  1. 首先找到数组中的最大值 maxVal
  2. 问题转化为：统计包含至少 k 个 maxVal 的子数组数目

算法步骤：

  1. 遍历数组，找到最大值
  2. 使用滑动窗口维护一个包含至少 k 个最大值的窗口
  3. 对于每个右端点，计算以该点为右端点且满足条件的子数组数量

滑动窗口策略：

  • 使用双指针 left 和 right
  • right 指针遍历数组，left 指针维护窗口左边界
  • 当窗口内最大值数量达到 k 时，所有以 left 为左端点或更左的位置为左端点、以 right 为右端点的子数组都满足条件
  • 答案累加 left + 1（表示有 left + 1 种选择左端点的方式）

时间复杂度：O(n)，空间复杂度：O(1)。这是最优解法。

代码实现

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int maxVal = *max_element(nums.begin(), nums.end());
        int n = nums.size();
        long long result = 0;
        int left = 0;
        int maxCount = 0;
        
        for (int right = 0; right < n; right++) {
            if (nums[right] == maxVal) {
                maxCount++;
            }
            
            while (maxCount >= k) {
                result += n - right;
                if (nums[left] == maxVal) {
                    maxCount--;
                }
                left++;
            }
        }
        
        return result;
    }
};

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        max_val = max(nums)
        n = len(nums)
        result = 0
        left = 0
        max_count = 0
        
        for right in range(n):
            if nums[right] == max_val:
                max_count += 1
            
            while max_count >= k:
                result += n - right
                if nums[left] == max_val:
                    max_count -= 1
                left += 1
        
        return result

public class Solution {
    public long CountSubarrays(int[] nums, int k) {
        int maxVal = nums.Max();
        int n = nums.Length;
        long result = 0;
        int left = 0;
        int maxCount = 0;
        
        for (int right = 0; right < n; right++) {
            if (nums[right] == maxVal) {
                maxCount++;
            }
            
            while (maxCount >= k) {
                result += n - right;
                if (nums[left] == maxVal) {
                    maxCount--;
                }
                left++;
            }
        }
        
        return result;
    }
}

var countSubarrays = function(nums, k) {
    const maxVal = Math.max(...nums);
    const n = nums.length;
    let result = 0;
    let left = 0;
    let maxCount = 0;
    
    for (let right = 0; right < n; right++) {
        if (nums[right]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)

相关题目