最多能完成排序的块 图解题解

把 0 到 n−1 的排列切块，最多能切几块

给一个长度为 n 的数组 arr，它恰好是 0 到 n−1 这 n 个数各出现一次的排列。把它切成若干连续的块，每块单独排序后再按原顺序拼起来，要让整个数组变成升序，问最多能切成多少块。题面例子 arr=[1,0,2,3,4]，答案是 4，切法是 [1,0] | [2] | [3] | [4]：头两个数排完序变 [0,1]，后面三个本来就各就各位，拼起来正好升序。

枚举每个切点验一遍，为什么会慢

能想到的笨办法是枚举所有切法：每两个数之间切或不切，切完把每段排序、拼回去，看整体是否升序。切点组合有 2 的 n−1 次方种，逐段排序验证，n 稍大就跑不动。得找只扫一遍、当场判断某位能不能切的办法。

前缀最大值追上下标，为什么就能放心切一刀

先抓住排列这个条件：数组是 0 到 n−1 的排列，整体排好序后，下标 i 上站的必然是数字 i。所以一个位置能不能当切口，就看它左边这一段排完序能不能刚好填回自己的位置。

维护一个前缀最大值 maxv，也就是从头扫到当前位置为止见过的最大数字。扫到下标 i 时，若 maxv 正好等于 i，说明 0 到 i 这 i+1 个数字已经全部出现在前 i+1 格里、正好填满 0 到 i 这些位置，左边这段排完序就是 0 到 i、和右边彻底分家，这一刀就能落下。贪心在这里落在前缀最大值这把尺子上：maxv 一追平当前下标就立刻封块切一刀、往后再攒下一段，切出的块数自然最多。

一个变量记前缀最大值，一趟扫完数块数

代码就两个变量：maxv 记前缀最大值、初值设 0，chunks 记切出的块数。从左往右扫，每到一格先用当前数字更新 maxv（谁大取谁），再判断 maxv 是否等于当前下标，相等就 chunks 加一。扫到头，chunks 就是答案。初值设 0 是因为排列里一定含 0，第一格若是 0 就能立刻切；更新和判断的先后也不能颠倒，先更新 maxv 再比下标，错一步就会多切或少切一块。

[1,0,2,3,4] 五个位置，maxv 各追到哪

下标 0，数字 1，maxv 更新成 1；maxv 是 1、下标是 0，不相等，数字 0 还没露面，这块封不了。下标 1，数字 0，maxv 还是 1；这回 maxv 等于下标 1，{0,1} 正好填满前两格，[1,0] 自成一块，chunks 记 1。下标 2，数字 2，maxv 变 2、等于下标 2，[2] 单独一块，chunks 记 2。下标 3、下标 4 同理，数字各是 3 和 4，maxv 每次都追平下标，各切一刀。一趟扫完，chunks 停在 4。

光比相邻两格，为什么判不出切点

常见的写错是只看相邻两个数的大小，或者拿最小值去判切点。可 [1,0,2,3,4] 里下标 0 不能切、下标 1 能切，靠相邻比较说不清缘由——真正决定能否封块的是左边整段的最大值有没有落回自己的位置，这是从头累计的全局信息，相邻两格看不出来。另一个坑是 maxv 初值：设成 arr[0] 或负数，再配上先比后更新，下标就会错开一位，多切或漏切。整套逻辑只扫一遍、只用两个变量，时间 O(n)、空间 O(1)。

Python

class Solution:
    def maxChunksToSorted(self, arr):
        max_so_far = 0
        chunks = 0
        for i in range(len(arr)):
            if arr[i] > max_so_far:
                max_so_far = arr[i]
            if max_so_far == i:        # 前缀最大值追平下标 → 切
                chunks += 1
        return chunks

C++

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int maxSoFar = 0, chunks = 0;
        for (int i = 0; i < (int)arr.size(); i++) {
            maxSoFar = max(maxSoFar, arr[i]);
            if (maxSoFar == i) chunks++;        // 追平就切
        }
        return chunks;
    }
};

Java

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int maxSoFar = 0, chunks = 0;
        for (int i = 0; i < arr.length; i++) {
            maxSoFar = Math.max(maxSoFar, arr[i]);
            if (maxSoFar == i) chunks++;        // 追平就切
        }
        return chunks;
    }
}