Skip to content

Latest commit

 

History

History
34 lines (29 loc) · 1.83 KB

统计最大元素出现至少K次的子数组.md

File metadata and controls

34 lines (29 loc) · 1.83 KB

统计最大元素出现至少 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 次。

解题思路

  • 首先找到最大元素max_ele,再找到最大元素后需要有一个变量count记录最大元素出现的次数,当count大于等于k时,开始计算子数组个数。
    while count == k:
        if nums[left] == max_ele:
            count -= 1
        left += 1
    ans += left
  • 这里最一开始编程错误,将ans放在了while里面更新, 即ans += 1,这种更新方式会漏掉答案。
  • ox3f题解原文如果此时 count=k,则不断右移左指针 left,直到窗口内的 max_ele 的出现次数小于 k 为止。对于右端点为 right 且左端点小于 left 的子数组,max_ele 的出现次数都至少为 k,把答案增加 left
  • 这里的意思是说如果在当前leftright状态下满足了条件,那么将left向左移包含更多的元素的子数组同样满足条件,这些子数组也是将ans放在了while里面更新漏掉的答案。那么为什么不加上right右侧的元素呢,因为right指针还在不断右移,在移动的过程中会重复计算。
    for x in nums:
  • 为什么for循环只需要nums中的数值不需要写right呢,因为这次更新答案不需要right了。