[LeetCode] 每日一题 2962. 统计最大元素出现至少 K 次的子数组（滑动窗口）

题目描述

给你一个整数数组 nums 和一个 正整数 k 。

请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。

子数组是数组中的一个连续元素序列。

题目链接

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

示例输入

示例 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

解题思路

这道题依然是典型的滑动窗口应用。最近做题的时候明显感觉到最近 LeetCode 每日一题有点像滑窗小专题，基本上思路都是围绕窗口的扩展和收缩进行优化。

题目要求找出子数组中最大元素出现至少 k 次的情况。思考过程可以分为两步：

1. 首先遍历一遍数组，找出整体的最大值 max。

2. 然后使用滑动窗口技巧，从左到右遍历数组，统计窗口中最大元素出现的次数 count。

   • 每当窗口中最大元素的数量达到或超过 k，就不断收缩左边界 left，直到 count < k。

   • 每次滑动到一个新位置，累加当前 left 的位置，代表以当前位置为右端点的所有符合要求的子数组数量。

这样单次遍历就可以动态维护答案，既高效又直观，非常符合最近滑窗题目的套路。

代码实现

class Solution {
    public long countSubarrays(int[] nums, int k) {
        long ans = 0;
        int max = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
        }
        int left = 0, count = 0;
        for (int num : nums) {
            if (num == max) {
                count++;
            }
            while (count >= k) {
                if (nums[left] == max) {
                    count--;
                }
                left++;
            }
            ans += left;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n) 🚀

  • 其中 n 是数组长度。一次遍历找最大值，另一次遍历滑动窗口处理，总共是线性时间

• 空间复杂度：O(1) 🌟

  • 只用了常数级别的变量，没有额外的空间开销

总结

这题可以说是标准的滑动窗口思路复现，思考过程中其实就和前几天遇到的滑窗优化套路非常像，关键是把窗口内的信息动态维护好，比如最大值出现次数 count，然后合理地收缩左指针 left。整体做下来感觉非常顺畅，算是加深了对滑动窗口这类题目的直觉理解👍

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。