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

https://leetcode.com/problems/count-subarrays-where-max-element-appears-at-least-k-times/description/

Leetcode - Count Subarrays Where Max Element Apperas at Least K Times

문제 유형 : 슬라이딩 윈도우

문제 난이도 : Medium

 

문제

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.

 

정수 배열 nums와 자연수 k를 받습니다.

nums배열의 최대 크기의 요소의 개수가 적어도 k개 이상 있는 부분배열의 개수를 구하시오.

 

풀이

아래는 영문 풀이입니다.

https://leetcode.com/problems/count-subarrays-where-max-element-appears-at-least-k-times/solutions/4940586/beats-99-61-c-easy-to-understand-constant-space-o-n-time/

 

슬라이딩 윈도우로 해결할 수 있습니다.

우선, 최대값을 구해야 합니다. nums 배열에서 최대 크기의 수를 구합니다. 이를 maxNum이라고 하겠습니다.

 

이제, 최소 크기의 부분 배열을 만들겠습니다. 

부분배열의 맨 오른쪽으로 가리키는 right을 0부터 시작합니다.

right을 1씩 늘려가면서 nums를 순회하며, 최대 크기의 수를 찾으면, 개수를 누적합니다.

누적된 개수가 k개가 될 때까지 반복합니다.

 

만약 right이 nums를 다 돌았는데도 최소 크기의 부분배열이 만들어지지 않았다면, 0을 반환합니다.

 

이제, 최소 크기의 부분배열을 확장해보겠습니다.

부분배열의 자를 수 있는 최대 앞부분의 인덱스를 limit이라고 하겠습니다.

right이 maxNum을 찾았다면, limit도 오른쪽으로 더 확장합니다. maxNum을 부분배열에서 하나 더 빼도 된다는 뜻이므로, limit이 다음의 maxNum을 찾을 때 까지 확장합니다.

확장이 끝나거나, 확장을 하지 않았다면, 부분배열의 개수에 limit만큼 누적시킵니다.

앞부분 에서 limit개만큼 자를 수 있으므로, 경우의 수는 limit만큼 추가된 것입니다.

이를 right이 nums를 다 돌때까지 반복합니다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        const int n = nums.size();
        long long ans = 0;
        int maxNum = *max_element(nums.begin(), nums.end());
        int freq = 0;
        int limit = 0;
        int right = 0;

        while(right < n) {
            if(nums[right] == maxNum) freq++;
            if(freq == k) break;
            right++;
        }

        if(freq < k) return 0;

        while(right < n) {
            bool found = false;
            if(nums[right] == maxNum) {
                found = true;
            }

            if(found) {
                while(limit < right && nums[limit] != maxNum) {
                    limit++;
                }
                limit++;
            }

            ans += limit;
            right++;   
        }

        return ans;
    }
};