LeetCode 2962 - 统计最大元素出现至少 K 次的子数组 - JZX 轻语

发表于 2025.05.01

滑动窗口的套路题目，窗口左侧每移动一位，右侧移到刚好满足条件，然后右侧后面所有的子数组都能满足条件，简单来说做法就是在每次（外层）循环中：

窗口左侧指针left向右移动一位；
窗口右侧指针right向右移动，直到窗口满足条件，此时所有以left为左端点、right直到n为右端点的子数组都满足条件；

class Solution {
public:
    using LL = long long;
    long long countSubarrays(vector<int>& nums, int k) {
        int max_val = *std::max_element(nums.begin(), nums.end());
        LL ans {0};
        int right = 0, cnt = 0, n = nums.size();
        for (int left = 0; left < n; ++left) {
            while (right < n && cnt < k) {
                if (nums[right++] == max_val) cnt++;
            }
            if (cnt == k) ans += n - right + 1;
            if (nums[left] == max_val) cnt--;
        }
        return ans;
    }
};