769。排序的最大區塊
難度：中
主題：陣列、堆疊、貪婪、排序、單調堆疊
給定一個長度為 n 的整數數組 arr，它表示 [0, n - 1] 範圍內整數的排列。
我們將 arr 分成一定數量的區塊（即分區），並單獨對每個區塊進行排序。連接它們後，結果應該等於排序後的陣列。
傳回我們可以對陣列進行排序的最大區塊數。
範例1：
-
輸入： arr = [4,3,2,1,0]
-
輸出： 1
-
說明：
- 分割成兩個或更多區塊將不會傳回所需的結果。
- 例如，拆分為 [4, 3], [2, 1, 0] 將得到 [3, 4, 0, 1, 2]，這是未排序的。
範例2：
-
輸入： arr = [1,0,2,3,4]
-
輸出： 4
-
說明：
- 我們可以分成兩個區塊，例如 [1, 0], [2, 3, 4]。
- 但是，分割成 [1, 0], [2], [3], [4] 是可能的最大區塊數。
約束：
- n == arr.length
- 1
- 0
- arr 的所有元素都是唯一。
提示：
- 第一個區塊可以作為最小的 k 找到，其中 A[:k 1] == [0, 1, 2, ...k]；然後我們重複這個過程。
解：
我們需要找到可以形成的最大區塊數，以便每個區塊都可以單獨排序，並且當連接時，結果是整個陣列的排序版本。
方法：
-
關鍵觀察：
- 陣列是從 0 到 n-1 的整數的排列。這個想法是遍歷數組並找到可以分隔區塊的位置。
- 如果對於區塊內的所有索引，直到該點的最大元素不超過原始排序數組中該點之後的最小元素，則可以對區塊進行排序。
-
策略：
- 追蹤從左向右遍歷時遇到的最大值。
- 在每個索引 i 處，檢查 i 之前的最大值是否小於或等於 i。如果這個條件成立，則表示您可以在該索引處拆分數組，因為左側部分可以獨立排序。
-
步驟：
- 迭代數組，同時保持運行最大值。
- 每當運行最大值等於目前索引時，就可以建立一個區塊。
- 計算這些區塊的數量。
讓我們用 PHP 實作這個解：769。排序的最大區塊數
<?php
/**
* @param Integer[] $arr
* @return Integer
*/
function maxChunksToSorted($arr) {
...
...
...
/**
* go to ./solution.php
*/
}
// Test cases
$arr1 = [4, 3, 2, 1, 0];
$arr2 = [1, 0, 2, 3, 4];
echo maxChunksToSorted($arr1); // Output: 1
echo "\n";
echo maxChunksToSorted($arr2); // Output: 4
?>
登入後複製
解釋：
-
初始化：
- 我們從 maxSoFar = -1 開始，以確保我們在遍歷數組時正確追蹤數組中的最大值。
-
chunks = 0 記錄可以形成的區塊的數量。
-
循環：
- 我們循環遍歷數組中的每個元素。
- 對於每個元素，我們將 maxSoFar 更新為目前元素與先前看到的最大值之間的最大值。
- 如果 maxSoFar == i，則表示索引 i 之前的陣列可以獨立排序，這是一個有效的區塊。
- 每次此條件成立時，我們都會增加區塊計數。
-
回傳：
時間複雜度：
-
時間複雜度： O(n)，其中 n 是陣列的長度。我們只遍歷數組一次。
-
空間複雜度： O(1)，因為我們只使用幾個變數來儲存中間結果。
演練範例：
對於 arr = [1, 0, 2, 3, 4]：
- 在索引 0 處，到目前為止遇到的最大值是 1。我們不能在這裡拆分。
- 在索引1處，最大值為1，與目前索引1匹配，因此我們可以分割成一個區塊。
- 在索引2處，最大值為2，它與索引2匹配，所以我們再次分裂。
- 在索引3處，最大值為3，它與索引3匹配，所以我們再次分裂。
- 在索引4處，最大值為4，它與索引4匹配，所以我們再次分裂。
因此，本例的輸出是 4，因為我們可以將其分成 4 個區塊。
聯絡連結
如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！
如果您想要更多類似的有用內容，請隨時關注我：
以上是。排序的最大區塊數的詳細內容。更多資訊請關注PHP中文網其他相關文章！
