tags: LeetCode,Python3,Medium

2962. Count Subarrays Where Max Element Appears at Least K Times

題目連結： Count Subarrays Where Max Element Appears at Least K Times

解題方向

• 初始化：
  • M 存儲數組 nums 中的最大元素。
  • n 是 nums 的長度。
  • cnt 用於記錄當前考慮的子數組中最大元素出現的次數。
  • ans 用來累加所有滿足條件的子數組的數量。
  • l 作為滑動窗口的左端點。
• 遍歷數組：
  • 使用 r 作為滑動窗口的右端點，從左向右遍歷數組。
  • 每當在位置 r 發現一個最大元素 M，cnt 就增加 1，表示當前窗口內最大元素的出現次數增加了。
• 調整左端點：
  • 當窗口內最大元素的出現次數 cnt 達到或超過 k 時，開始移動窗口的左端點 l，直到 cnt 再次小於 k。這是通過一個 while 迴圈實現的。如果左端點指向的是最大元素 M，則將 cnt 減 1，並將左端點 l 右移。
• 計算子數組數量：
  • 對於每個位置 r（即每個可能的窗口的右端點），計算有多少個以 r 為右端點的子數組滿足條件（即最大元素出現至少 k 次）。這個數量正好等於窗口的左端點 l 的位置，因為從數組的起點到 l-1 的任何位置開始的子數組，加上從 l 到 r 的部分，都將包含至少 k 個最大元素 M。
  • 通過累加 l 的值到 ans，我們就能計算出所有以 r 為右端點的滿足條件的子數組數量。

完整程式碼

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        M=max(nums)
        n=len(nums)
        cnt=ans=l=0
        for r in range(n):
            if nums[r]==M: cnt+=1
            while cnt>=k:
                if nums[l]==M: cnt-=1
                l+=1
            ans+=l
        return ans