769. 最多能完成排序的塊 : 簡單模拟題（循環不變）

題目描述

這是 LeetCode 上的 ​​769. 最多能完成排序的塊​​ ，難度為 中等。

Tag : 「模拟」

給定一個長度為 ​

​n​

​​ 的整數數組 ​

​arr​

​​ ，它表示在

我們将 ​

​arr​

​ 分割成若幹 塊 (即分區)，并對每個塊單獨排序。将它們連接配接起來後，使得連接配接的結果和按升序排序後的原數組相同。

傳回數組能分成的最多塊數量。

示例 1:

輸入: arr = [4,3,2,1,0]

輸出: 1

解釋:
将數組分成2塊或者更多塊，都無法得到所需的結果。
例如，分成 [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]      

提示:

• ​

  ​arr​

  ​ 中每個元素都 不同

模拟

本題考察的是簡單模拟能力，或者說是簡單的對「循環不變量」的設計。

我們從前往後處理所有的 （即 ​​

​i​

​​ 定義為目前劃分塊的右邊界下标），處理過程中定義變量 ​

​j​

​​ 為目前劃分塊的左邊界下标（初始值為 ），定義 ​​

​min​

​​ 為目前劃分塊中元素最小值（初始值為 或 ），定義 ​​

​max​

​​ 為目前劃分塊中元素最大值（初始值為 或 ）。

當且僅當 且 時，下标範圍 排序結果為 ，此時塊的個數加一，并重新初始化幾個變量，繼續循環統計下個塊的資訊。

Java 代碼：

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length, ans = 0;
        for (int i = 0, j = 0, min = n, max = -1; i < n; i++) {
            min = Math.min(min, arr[i]);
            max = Math.max(max, arr[i]);
            if (j == min && i == max) {
                ans++; j = i + 1; min = n; max = -1;
            }
        }
        return      

TypeScript 代碼：

function maxChunksToSorted(arr: number[]): number {
    let n = arr.length, ans = 0
    for (let i = 0, j = 0, min = n, max = -1; i < n; i++) {
        min = Math.min(min, arr[i])
        max = Math.max(max, arr[i])
        if (j == min && i == max) {
            ans++; j = i + 1; min = n; max = -1;
        }
    }
    return      

Python 代碼：

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        n, ans = len(arr), 0
        j, minv, maxv = 0, n, -1
        for i in range(n):
            minv, maxv = min(minv, arr[i]), max(maxv, arr[i])
            if j == minv and i == maxv:
                ans, j, minv, maxv = ans + 1, i + 1, n, -1
        return      

• 時間複雜度：
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.769​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。