連續子數組

2762。連續子數組

難度：中

主題：滑動視窗、陣列、有序集、堆疊（優先權佇列）、佇列、單調佇列、兩個指標、有序映射、雜湊表、動態規劃、計數、數學、二元搜尋樹、線段樹、樹、堆疊、二分搜尋、單調堆疊、記憶、迭代器、貪婪、深度優先搜尋、遞歸

給你一個0索引整數數組nums。如果滿足以下條件，則 nums 的子數組稱為連續的：

• 設 i, i 1, ..., j 為子數組中的索引。然後，對於每對索引i 1, i₂ 1] - nums[i₂]|

傳回連續子數組的總數。

子數組是數組中連續的非空元素序列。

範例1：

• 輸入： nums = [5,4,2,4]
• 輸出： 8
• 說明：
  • 大小為 1 的連續子數組：[5]、[4]、[2]、[4]。
  • 大小為 2 的連續子數組：[5,4]、[4,2]、[2,4]。
  • 大小為 3 的連續子數組：[4,2,4]。
  • 沒有尺寸為 4 的子數組。
  • 連續子數組總數 = 4 3 1 = 8。
  • 可以證明不再有連續的子數組。

範例2：

• 輸入： nums = [1,2,3]
• 輸出： 6
• 說明：
  • 大小為 1 的連續子數組：[1]、[2]、[3]。
  • 大小為 2 的連續子數組：[1,2], [2,3].
  • 大小為 3 的連續子數組：[1,2,3]。
  • 連續子數組總數 = 3 2 1 = 6。

約束：

• 1 5
• 1 9

提示：

1. 嘗試使用滑動視窗技術。
2. 使用集合或映射來追蹤子數組的最大值和最小值。

解：

我們可以使用滑動視窗技術來高效率計算連續子數組的數量。我們將維護一個有效窗口，其中子數組中的最大值和最小值之差最多為 2。為了有效追蹤目前視窗內的最大值和最小值，我們可以使用兩個 deques （一個一個為最大值，一個為最小值）。

方法

1. 使用兩個指標的滑動視窗技術：左和右。
2. 使用兩個雙端隊列：
   • 用於按降序追蹤元素索引以獲得最大值。
   • 用於按升序追蹤元素索引以獲得最小值。
3. 對於每個索引權：
   • 更新雙端佇列以反映目前視窗。
   • 確保視窗保持有效（最大值和最小值之差 ≤ 2）。如果無效，則增加左指標以縮小視窗。
   • 計算以索引 right 結尾的有效子數組的數量（右 - 左 1）。
4. 傳回子數組的總數。

讓我們用 PHP 實作這個解決方案：2762。連續子數組

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function continuousSubarrays($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$nums1 = [5, 4, 2, 4];
echo continuousSubarrays($nums1) . "\n"; // Output: 8

$nums2 = [1, 2, 3];
echo continuousSubarrays($nums2) . "\n"; // Output: 6
?>

解釋：

1. 滑動視窗：
   
   只有當視窗無效（即最大值與最小值之差超過2）時，左指標才會向前移動。右指針透過遍歷數組來擴展視窗。

2. 最大值和最小值的雙端隊列：

   • maxDeque 總是會依照降序儲存元素索引，確保目前視窗中的最大值位於前方 (maxDeque[0])。
   • minDeque 始終按升序保存元素索引，確保目前視窗中的最小值位於前面 (minDeque[0])。

3. 計算子數組：
   
   對於每個右側，以右側結尾的有效子數組的數量等於（右 - 左 1），因為從左到右的所有子數組都是有效的。

4. 效率：
   
   每個元素最多會加入雙端佇列或從雙端佇列中刪除一次，使得時間複雜度 O(n)。由於雙端隊列，空間複雜度為 O(n)。

輸出

8
6

複雜性分析

1. 時間複雜度：

   • 每個元素最多從雙端佇列中推送和彈出一次。
   • 總時間複雜度為O(n)。

2. 空間複雜度：

   • 雙端佇列儲存索引，最大大小為n。
   • 空間複雜度為O(n)。

此實作非常高效，並且在提供的約束範圍內工作。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是連續子數組的詳細內容。更多資訊請關注PHP中文網其他相關文章！