2962. Count Subarrays Where Max Element Appears at Least K Times

難度: Medium

類型: Array, Sliding Window

CPP程式下載: 2962.cpp

前情題要:

在nums內最大值出現K次的 subarray 有幾個

You are given an integer array nums and a positive integer k.

Return the number of subarrays where the maximum element of nums appears at least k times in that subarray.

A subarray is a contiguous sequence of elements within an array.

 

Example 1:

Input: nums = [1,3,2,3,3], k = 2
Output: 6
Explanation: The subarrays that contain the element 3 at least 2 times are: [1,3,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3] and [3,3].

Example 2:

Input: nums = [1,4,2,1], k = 3
Output: 0
Explanation: No subarray contains the element 4 at least 3 times.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 106
• 1 <= k <= 105

思考方式:

1. 找出最大值, 並記錄最大值的位置和次數。

2. 計算含K次最大值的subarray個數:

    2-1. 從第一個最大值開始共K次, 中間不變, 但頭可以從 index 0 到出現第一次的index都可以選, 尾可以從第K次到nums的最後。

    2-2. 從第 i 個最大值開始到第 i+K-1 個最大值, 中間不變, 但頭可以從 i-1 個最大值後一個index開始到第 i 個最大值的index都可以選, 尾可以從第 i+k-1 個最大值的index直到nums的最後。

複雜度思考:

Time Complexity: O( N ) 

Space Complexity: O( max. is N * sizeof(int))

結果:

Runtime: 0 ms, Beats: 100%

Memory: 135.29 MB, Beats: 8.62%

Accepted

634 / 634 testcases passed

tendchen

submitted at Jun 11, 2025 10:39

Runtime

0ms

Beats100.00%

Analyze Complexity

Memory

135.29MB

Beats8.62%

Analyze Complexity

Code

C++

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int nums_size=nums.size();
        vector<int> indexV;
        int max_val=nums[0];
        indexV.push_back(0);
        int max_times=1;
        long long output;
        for (int i=1;i<nums_size;i++)
        {
            if (nums.at(i)>max_val)
            {
                max_val=nums.at(i);
                max_times=1;
                indexV.clear();
                indexV.push_back(i);
            }
            else if (nums.at(i)==max_val)
            {
                indexV.push_back(i);
                max_times++;
            }
        }
        if (max_times<k) return 0;
        //printf("%d * %d\n",(a[i]+1),(numsSize-a[i+k-1]));
        output=(long long)(indexV[0]+1)*(long long)(nums_size-indexV[k-1]);
        for (int i=1;i<=max_times-k;i++)
        {
            //printf("%d * %d\n",(a[i]-a[i-1]),(numsSize-a[i+k-1]));
            output=output+(indexV[i]-indexV[i-1])*(long long)(nums_size-indexV[i+k-1]);
            //printf("(%d)output=%d\n",i,output);
        }
        return output;
    }
};