计算最大元素出现至少K次滑动窗口的子数组

Question

问题

计算最大元素出现至少 K 次的子数组

您将获得一个整数数组

nums

和一个正整数

k

。返回

nums

的最大元素在该子数组中至少出现

k

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

逻辑

• 穿过窗户，如果目前您的窗户少于

  k maxElement counts

  ，请继续扩大窗户
• 如果您有

  more than equal to k maxElement counts

  ，请增加

  ans

  并努力缩短/滑动窗口

代码

class Solution:

    def countSubarrays(self, nums: List[int], k: int) -> int:
        i = j = 0
        count = 0
        ans = 0 
        N = len(nums)
        max_element = max(nums)
    
        while j < N:
            # keep increasing the window
            if count < k:
                count+= nums[j] == max_element
                j+=1
            # slide/decrease the window
            else:
                ans+=1
                if nums[i] == max_element:
                    count-=1
                i+=1
    
        return ans
            

问题

可能出现的问题是

• 我没有考虑可以缩短的最后一个子数组，或者至少考虑添加到

  ans

  变量中。
• 我没有正确滑动窗户，因为我可以向右也可以向左走。考虑

  nums = [1,3,2,3,3]

  和 K 当前子数组是

  [3,2,3]

  我已经满足了

  count >= k

  所以我不会考虑

  [3,2,3,3]

  我会致力于缩短子数组。
• 我知道我可以强制执行 while 循环（while count>=k 递增 i 直到这个协议被打破），但我相信这仍然不能解决问题。这在 if 条件下仍然可能发生（如果 count >=k 并冻结 j 直到协议被打破），因此，任何帮助都是值得赞赏的。我希望我们能找到一个解决方案，如果 count >=k 我们不会增加 j 直到我们恢复 count < k and continue increasing j later
• 如果您需要特定情况，此代码将在

  nums=[1,3,2,3,3] and k = 2 Output = 2 Expected Output = 6

  处失败，两个子数组为

  [1, 3, 2, 3] and [3, 2, 3]

Answer 1

问题出在

else

子句中，您只需增加结果即可。但实际上所有从

i

开始、结束索引为

>= j

的子数组都满足条件。因此，您必须做

ans += 1

，而不是

ans += N - j

。除此之外，你的算法看起来不错。