# 資訊

:::info
- Question: 2962. Count Subarrays Where MAx Element Appears At Least K Times
- From: Leetcode Daily Challenge 2024.03.29
- Difficulty: Medium
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

You are given an integer array `nums` and a positive integer `k`.

Return the number of subarrays where the maximum element of `nums` appears at least `k` times in that subarray.

A **subarray** is a contiguous sequence of elements within an array.

> Example 1:
:::success
* Input: `nums = [1,3,2,3,3]`, `k = 2`
* Output: 6
* Explanation: The subarrays that contain the element 3 at least 2 times are: `[1,3,2,3]`, `[1,3,2,3,3]`, `[3,2,3]`, `[3,2,3,3]`, `[2,3,3]` and `[3,3]`.
:::

> Example 2:
:::success
* Input: `nums = [1,4,2,1]`, `k = 3`
* Output: 0
* Explanation: No subarray contains the element 4 at least 3 times.
:::

> Constraints:
:::success
1 <= `nums.length` <= $10^5$
1 <= `nums[i]` <= $10^6$
1 <= `k` <= $10^5$
:::

---

# 解法

## 概念

跟昨天很像，用 sliding window 就是要維持視窗中的某個性質，以這題來說，window 裡面就是保持元素出現 k 次，然後以起始的 `l` 作為計算 subarray 的基準

這邊第 15 - 19 行其實有點多餘，因為我維持 window 裡面 max element 出現次數都 `<= k`，代表這邊其實不會走到，那些包含 k 次以上的 subarray 並不會以 window 形式呈現，而是直接在第 26 行直接加上去而已

## 程式碼

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        # Parameters I need
        l = 0
        r = 1
        ans = 0
        count = 0
        n = len(nums)
        standard = max(nums)    # <-- cost O(n) :(

        if nums[l] == standard:
            count += 1

        while l < n:
            # If the interval contains the max element more than k times
            while count > k and r > l:
                if nums[r] == standard:
                    count -= 1
                r -= 1

            while r < n and count < k:
                if nums[r] == standard:
                    count += 1
                r += 1
            if count == k:
                ans += (n - r + 1)    # <-- Another interval found

            # Move l
            if nums[l] == standard:
                count -= 1
            l += 1
        return ans

---

# 複雜度

## 時間複雜度

為了找最大值使用了一次 max，為了取長度用了一次 len，這樣算是 $O(n)$，接著做 sliding window 也花了 $O(n)$，整體是 $O(3n) = O(n)$


## 空間複雜度

空間的部分就是常數空間，所以是 $O(1)$