連續子數組-php教程-PHP中文網

連續子數組

Mary-Kate Olsen

發布： 2024-12-25 05:46:15

原創

830 人瀏覽過

Continuous Subarrays

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。

約束：

提示：

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

解：

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

方法

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

讓我們用 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
?>

登入後複製

解釋：

滑動視窗：

只有當視窗無效（即最大值與最小值之差超過2）時，左指標才會向前移動。右指針透過遍歷數組來擴展視窗。
最大值和最小值的雙端隊列：
- maxDeque 總是會依照降序儲存元素索引，確保目前視窗中的最大值位於前方 (maxDeque[0])。
- minDeque 始終按升序保存元素索引，確保目前視窗中的最小值位於前面 (minDeque[0])。
計算子數組：

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

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