題目

給你一個整數數組?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. 設 mx=max(nums)。
2. 元素 x=nums[right] 進入窗口時，如果 x=mx，把計數器 cntMx 加一。
3. 如果 cntMx=k，則不斷右移左指針 left，直到窗口中的 mx 的出現次數小于 k 為止。
4. 內層循環結束后，[left,right] 這個子數組是不滿足題目要求的，但在退出循環之前的最后一輪循環，[left?1,right] 是滿足題目要求的。由于子數組越長，越能滿足題目要求，所以除了 [left?1,right]，還有 [left?2,right],[left?3,right],…,[0,right] 都是滿足要求的。也就是說，當右端點固定在 right 時，左端點在 0,1,2,…,left?1 的所有子數組都是滿足要求的，這一共有 left 個，加到答案中。

作者：靈茶山艾府
鏈接：https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times/solutions/2560940/hua-dong-chuang-kou-fu-ti-dan-pythonjava-xvwg/
來源：力扣（LeetCode）

答案

這里我自己AC的寫法和靈神的有一點不一樣，分別如下：

自己的寫法：

class Solution:def countSubarrays(self, nums: List[int], k: int) -> int:m = max(nums)n = len(nums)if k > n:return 0left = 0ans = 0count = 0for right, x in enumerate(nums):    # 移動右指針，擴大窗口if x == m:count += 1    # 更新最大元素出現次數while count == k:    # 滿足最大元素出現k次時ans += n - right    # 從[left...right]到[left...n-1]這些子數組都滿足if nums[left] == m:    # 如果左端點元素等于最大元素count -= 1    # 移動左指針前，將最大元素出現次數減1left += 1    # 移動左指針，縮小窗口return ans

靈神的寫法：

class Solution:def countSubarrays(self, nums: List[int], k: int) -> int:m = max(nums)n = len(nums)if k > n:return 0left = 0ans = 0count = 0for right, x in enumerate(nums):    # 移動右指針，擴大窗口if x == m:count += 1while count == k:    # 滿足最大元素出現k次時，持續移動左指針if nums[left] == m:    # 如果左端點元素等于最大元素count -= 1    # 移動左指針前，將最大元素出現次數減1left += 1ans += left    # 從[0...right]到[left-1...right]都滿足return ans

復雜度分析

時間復雜度：O(n)，其中 n 為 nums 的長度。雖然寫了個二重循環，但是內層循環中對 left 加一的總執行次數不會超過 n 次，所以總的時間復雜度為 O(n)。
空間復雜度：O(1)。

作者：靈茶山艾府
鏈接：https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times/solutions/2560940/hua-dong-chuang-kou-fu-ti-dan-pythonjava-xvwg/
來源：力扣（LeetCode）