LeetCode 题解工作台
统计最大元素出现至少 K 次的子数组
给你一个整数数组 nums 和一个 正整数 k 。 请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。 子数组是数组中的一个连续元素序列。 示例 1： 输入： nums = [1,3,2,3,3], k = 2 输出： 6 解释： 包含元…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 滑动窗口（状态滚动更新）
答案摘要
不妨记数组中的最大值为 。 我们用两个指针 和 维护一个滑动窗口，使得 $[i, j)$ 之间的子数组中，有 个元素等于 。如果我们固定左端点 ，那么所有大于等于 的右端点都满足条件，一共有 $n - (j - 1)$ 个。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
给你一个整数数组 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 <= 1051 <= nums[i] <= 1061 <= k <= 105
解题思路
方法一：双指针
不妨记数组中的最大值为 。
我们用两个指针 和 维护一个滑动窗口，使得 之间的子数组中，有 个元素等于 。如果我们固定左端点 ，那么所有大于等于 的右端点都满足条件，一共有 个。
因此，我们枚举左端点 ，用指针 维护右端点，用一个变量 记录当前窗口中等于 的元素个数，当 大于等于 时，我们就找到了满足条件的子数组，将答案增加 。然后我们更新 ，继续枚举下一个左端点。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
mx = max(nums)
n = len(nums)
ans = cnt = j = 0
for x in nums:
while j < n and cnt < k:
cnt += nums[j] == mx
j += 1
if cnt < k:
break
ans += n - j + 1
cnt -= x == mx
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Look for the candidate’s ability to apply the sliding window pattern effectively.
- question_mark
Evaluate if the candidate is keeping track of the state of the maximum element efficiently.
- question_mark
Check if the candidate understands the importance of dynamic window adjustment to avoid redundant work.
常见陷阱
外企场景- error
Failing to dynamically adjust the window size, which may lead to unnecessary calculations.
- error
Not properly keeping track of the frequency of the maximum element, resulting in missed subarrays.
- error
Overcomplicating the solution by not leveraging the sliding window technique, which could lead to slower performance.
进阶变体
外企场景- arrow_right_alt
Instead of finding subarrays with the maximum element appearing at least k times, find subarrays where the maximum element appears exactly k times.
- arrow_right_alt
Change the problem to count subarrays where the sum of the elements equals a certain value, using a sliding window approach.
- arrow_right_alt
Consider solving the problem with a different constraint, such as finding subarrays where the maximum element appears at most k times.