題目資訊

題目編號: 2444
題目連結: Count Subarrays With Fixed Bounds
主題: Array, Queue, Sliding Window, Monotonic Queue

題目敘述

你被給予一個整數陣列 nums 和兩個整數 minK 和 maxK。

一個 固定邊界子陣列 是指滿足以下條件的 nums 的子陣列：

子陣列中的最小值等於 minK。
子陣列中的最大值等於 maxK。

返回固定邊界子陣列的數量。

一個 子陣列 是一個數組中的連續部分。

範例 1:

輸入: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
輸出: 2
解釋: 固定邊界子陣列有 [1,3,5] 和 [1,3,5,2]。

範例 2:

輸入: nums = [1,1,1,1], minK = 1, maxK = 1
輸出: 10
解釋: nums 的每一個子陣列都是固定邊界子陣列。共有10個可能的子陣列。

約束條件:

$2 \leq \text{nums.length} \leq 10^5$
$1 \leq \text{nums}[i], \text{minK}, \text{maxK} \leq 10^6$

直覺

這個問題要求我們在給定的數組 nums 中計數滿足條件的子數組，這些子數組的最小值和最大值分別等於指定的整數 minK 和 maxK。通過暴力檢查所有可能的子數組的方法將會非常低效，特別是在輸入規模很大的情況下。因此，我們需要一種以線性時間複雜度運行的高效方法，透過遍歷數組並使用指標來記錄感興趣的位置。

解法

這個算法透過單次遍歷 nums 數組，來有效地計數符合固定邊界條件的子數組。具體步驟如下：

初始化：
- 初始化 result 來存儲有效子數組的數量。
- 定義 lastInvalidIndex 來記錄最近的一個元素範圍超出 [minK, maxK] 的位置。
- 設定 minKIndex 和 maxKIndex 來跟踪數組中 minK 和 maxK 最近出現的位置。
遍歷數組：
- 對於 nums 中每個索引 right 的元素，執行以下操作：
  - 範圍檢查：如果 nums[right] 超出 [minK, maxK] 的範圍，更新 lastInvalidIndex 為 right，並將 minKIndex 和 maxKIndex 重置為 -1，因為當前元素不能成為有效子數組的一部分。
  - 更新最小值索引：如果 nums[right] 等於 minK，更新 minKIndex 為 right。
  - 更新最大值索引：如果 nums[right] 等於 maxK，更新 maxKIndex 為 right。
  - 計算子數組數量：當 minK 和 maxK 均被發現（minKIndex != -1 && maxKIndex != -1），計算以 right 結尾的有效子數組的數量。這些子數組的數量可以通過差 min(minKIndex, maxKIndex) - lastInvalidIndex 得到。
計數子數組：變量 result 在遍歷 nums 過程中累加所有有效子數組的數量。
返回結果：最終返回 result，其包含了所有符合固定邊界條件的子數組的總數量。

此方法確保每個元素的處理時間為常數時間，導致整體時間複雜度為 $O(n)$，其中 $n$ 是 nums 的長度。這在給定的限制下是非常高效的，允許該解決方案有效地處理大規模數據輸入。

程式碼

C++

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        long long result = 0;
        int lastInvalidIndex = -1; // 最後一個不在範圍 [minK, maxK] 的元素索引
        int minKIndex = -1;        // 陣列中最近一次出現 minK 的索引
        int maxKIndex = -1;        // 陣列中最近一次出現 maxK 的索引

        for (int right = 0; right < nums.size(); ++right) {
            // 如果當前元素超出有效範圍，重置索引
            if (nums[right] < minK || nums[right] > maxK) {
                lastInvalidIndex = right;
                minKIndex = -1;
                maxKIndex = -1;
                continue;
            }

            // 如果當前元素是 minK，更新 minKIndex
            if (nums[right] == minK) {
                minKIndex = right;
            }

            // 如果當前元素是 maxK，更新 maxKIndex
            if (nums[right] == maxK) {
                maxKIndex = right;
            }

            // 如果在當前範圍內找到 minK 和 maxK
            if (minKIndex != -1 && maxKIndex != -1) {
                // 決定以 'right' 結束的有效子陣列的數量
                result += max(0, min(minKIndex, maxKIndex) - lastInvalidIndex);
            }
        }

        return result;
    }
};

Python

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        result = 0
        lastInvalidIndex = -1  # 最後一個不在範圍 [minK, maxK] 的元素的索引
        minKIndex = -1         # 最近一次出現的 minK 在陣列中的索引
        maxKIndex = -1         # 最近一次出現的 maxK 在陣列中的索引

        for right in range(len(nums)):
            # 如果當前元素不在有效範圍內，重設索引
            if nums[right] < minK or nums[right] > maxK:
                lastInvalidIndex = right
                minKIndex = -1
                maxKIndex = -1
                continue

            # 如果當前元素是 minK，更新 minKIndex
            if nums[right] == minK:
                minKIndex = right

            # 如果當前元素是 maxK，更新 maxKIndex
            if nums[right] == maxK:
                maxKIndex = right

            # 如果在當前範圍內找到了 minK 和 maxK
            if minKIndex != -1 and maxKIndex != -1:
                # 決定以 'right' 結尾的有效子陣列的數量
                result += max(0, min(minKIndex, maxKIndex) - lastInvalidIndex)

        return result

複雜度分析

時間複雜度: $O(n)$
該演算法僅用一個迴圈遍歷整個陣列 nums 一次，因此時間複雜度為 $O(n)$，其中 $n$ 為陣列的長度。迴圈中的每個操作，例如條件檢查和索引更新，所需的時間為常數時間 $O(1)$。因此，總體複雜度線性地取決於輸入陣列的大小。
空間複雜度: $O(1)$
該演算法使用恒定量的額外空間。所需的空間不依賴於輸入 nums 的大小，僅涉及幾個整數變數（result、lastInvalidIndex、minKIndex 和 maxKIndex）。因此，空間複雜度為 $O(1)$。

CS Note
En

Leetcode 2444. Count Subarrays With Fixed Bounds

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析