題目資訊

題目編號: 2962
題目連結: Count Subarrays Where Max Element Appears at Least K Times
主題: Array, Sliding Window

題目敘述

你被給定一個整數陣列 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 \leq nums.length \leq 10^5$
$1 \leq nums[i] \leq 10^6$
$1 \leq k \leq 10^5$

直覺

此問題的核心在於識別給定數組 nums 中的子數組，其中最大元素至少出現 k 次。經過分析，可以觀察到，這個任務實質上是如何藉由高效的搜尋策略來管理最大元素在潛在子數組中的出現次數。

解法

為了解決此問題，我們採用雙指針法，該方法能夠高效地掃描整個數組以檢查符合條件的子數組。以下是解決步驟的詳細分解：

識別最大元素: 首先，在數組 nums 中找出最大元素。這可以在 $O(n)$ 的時間內通過掃描整個數組一次來完成。
初始化計數器: 設置變量以追蹤最大元素的出現次數 (count) 和符合條件的子數組的總數 (result)。這兩個計數器都初始化為零。
雙指針技術: 我們採用雙指針技術，該方法涉及維持一個由兩個指標（left 和 right）組成的窗口來探索潛在子數組。
- 將兩個指針均起始於數組的開頭。逐步增大 right 指針的指向位置，藉此擴展窗口以包含每一個新的元素。
- 當遇到等於最大元素的元素時，增加 count。
調整左邊界: 當子數組包含超過 k 次的最大元素時，調整 left 指針位置，以確保子數組從最早可能的位置開始。這能保證 count 是有效的，即在當前窗口內對最大元素的計算是準確的。
計算有效子數組: 對於每個 right 指針的位置，如果最大元素 (count) 的數量大於或等於 k，那麼從 0 到 left 再到 right 的每個子數組都是有效的。我們將這些子數組的數量（left + 1）加到 result 中。
遍歷整個數組: 繼續這個過程直到 right 指針已經遍歷完整個數組，確保所有的子數組都被考慮在內。

這種方法有效地管理了在子數組中保證至少存在 k 個最大元素的限制，並以 $O(n)$ 的時間複雜度運行，這在給定限制下是最佳的。

程式碼

C++

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        // 找出陣列中的最大元素
        long long maxElement = *max_element(nums.begin(), nums.end());
        
        // 初始化計數器以計算出現次數和結果
        long long count = 0, result = 0;
        
        // 使用雙指標技術探索所有子陣列
        for (int left = 0, right = 0; right < nums.size(); right++) {
            // 若當前元素為最大元素則增加計數
            count += nums[right] == maxElement;
            
            // 調整左邊界以確保至少有 'k' 個最大元素
            while (count - (nums[left] == maxElement) >= k) {
                count -= nums[left++] == maxElement;
            }
            
            // 如果當前子陣列至少有 'k' 個最大元素，計算以 right 結尾的所有子陣列
            if (count >= k) {
                result += left + 1;
            }
        }
        
        return result;
    }
};

Python

class Solution:
    def countSubarrays(self, nums, k):
        # 確定數組中的最大元素
        maxElement = max(nums)
        
        # 初始化計數器以計算出現次數和結果
        count = 0
        result = 0
        
        # 雙指針技術探索所有子數組
        left = 0
        for right in range(len(nums)):
            # 如果當前元素是最大元素，增加計數
            count += nums[right] == maxElement
            
            # 調整左邊界，以擁有至少 'k' 個最大元素
            while count - (nums[left] == maxElement) >= k:
                count -= nums[left] == maxElement
                left += 1
            
            # 如果當前子數組至少有 'k' 個最大元素，計算所有以 right 結尾的子數組
            if count >= k:
                result += left + 1
        
        return result

複雜度分析

時間複雜度: $O(n)$
此解法採用雙指針方法，其中 right 指針遍歷陣列，而 left 指針調整以維持當前子陣列中至少存在 k 個最大元素。移動 left 指針可確保每個元素被恆定次數地考慮，使得對陣列中每個元素的遍歷工作量為每個元素固定量的工作。因此，時間複雜度由對陣列的單次遍歷決定，為 $O(n)$，其中 $n$ 為輸入陣列 nums 中的元素數量。
空間複雜度: $O(1)$
空間複雜度為恆定，$O(1)$，因為此解法無論輸入大小如何，只使用固定量的額外空間。具體來說，變數如 maxElement、count、result 以及索引 left 和 right 被使用，所有這些都佔用與陣列大小無關的恆定空間。沒有使用隨輸入大小擴展的額外數據結構。

CS Note
En

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

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析