个人博客有哪些网站,文化建设的重要性,外贸网站seo,wordpress 静态规则2962. 统计最大元素出现至少 K 次的子数组 给你一个整数数组 nums 和一个 正整数 k 。 请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组#xff0c;并返回满足这一条件的子数组的数目。 子数组是数组中的一个连续元素序列。 示例 1#xff1a; 输入#…2962. 统计最大元素出现至少 K 次的子数组 给你一个整数数组 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 105 1 nums[i] 106 1 k 105 题解
如标题所示本题采用滑动数组进行解题
题目要求所有满足条件的子数组 那么我们自然需要考虑所有的子数组 我们该如何做到呢
首先看看如何枚举所有的子数组 我们可以用一个循环枚举出所有子数组可能的开头然后内层再写一个循环枚举所有可能的结尾这样就枚举了所有的子数组
那么滑动数组又该如何考虑到所有的子数组呢 类似的我们可以写一个循环枚举出所有子数组的结尾 i 然后使用指针 l0 作为子数组的开头那么 l 与 i 就是滑动窗口的区间 我们使用变量 count 记录滑动窗口中的最大值的个数res0 记录返回值 此时 i 作为窗口的右边不断右移 当 count k 时此时的滑动窗口满足条件我们找到了一个答案
但是问题是接下来我们要如移动滑动窗口呢 将 i 向右移还是将 l 向右移
注意到我们第一层循环是枚举所有子数组的结尾 只要对于每一种结尾我们都找到所有可能的子数组就能解决问题 但是我们显然不能枚举开头 l 否则与枚举就一样了时间复杂高 当 count k 时我们可以将 窗口左边 l 右移直到 count ! k 那么对于此时的 i 此时所有以 l 的左边为开头的子数组 [ l, i ] 都是满足条件的 也就是我们找到了以 i 结尾的所有满足条件的子数组 所以滑动窗口 [ l, i ] 的含义就是以 i 结尾的第一个不满足条件的子数组 resl 枚举下一个 i 如果 count ! k那么 l 的位置不变resl 如果countk那么接着移动 l 直到滑动窗口不满足条件
总计滑动窗口划过一次数组时间复杂度为 O(n) 代码如下↓
long long countSubarrays(int* nums, int numsSize, int k) {int l0;int max0;long res0;int count0;for(int i0;inumsSize;i){if(nums[i]max){maxnums[i];}}for(int i0;inumsSize;i){if(nums[i]max){count;}while(countk)//怎么说呢每次i就是子数组的右端点每次当count的个数为k的时候就将l右移直到countk那么l之前的所有字符都可以作为子数组的左端点也就是说以i为右端点的满足条件的子数组有left个。然后i继续右移直到count再次k然后重复以上过程left左边的所有字符同样满足条件count的个数肯定k所以resleft{if(nums[l]max){count--;}l;}resl;printf(%d\n,l);}return res;
}
