LeetCode 769. 最多能完成排序的块

2025-07-07 HGNULB 约 9 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 769. 最多能完成排序的块

题意分析

给一个长度为 n 的数组 arr，它恰好是 $0$ 到 $n-1$ 的一个排列。要求把数组切成若干连续的块，对每一块单独做升序排序，然后按原顺序把这些块拼接回去，最终结果必须是完全升序的 $[0, 1, \dots, n-1]$。问最多能切成多少块。

题面里「数组是 $0$ 到 $n-1$ 的排列」这句话是全部信息的来源，绝不能当成无关背景。它带来两条极强的性质：值和下标取自同一个集合，因此排好序之后位置 i 上的值必然恰好是 i；而且没有重复元素，不需要考虑相等值的归属问题。

「最多能切多少块」看似是个优化问题，但仔细想会发现它其实是个局部判定问题：切点越多越好，而两个相邻块之间能否切开，只取决于该切点两侧的元素是否已经「各归其位」。所以真正要回答的是「有多少个位置可以作为块的右边界」。

边界上要覆盖：数组已经完全有序（每个位置都能切，答案是 n）；数组是完全逆序（如 [4,3,2,1,0]，只能整块，答案是 $1$）；只有一个元素（答案是 $1$）；前半段有序后半段乱（如 [0,1,3,2]，答案是 $3$）。数组长度上限是 $10$，规模极小，所以本题考的完全是能不能看穿判定条件，而不是效率。

解法：前缀最大值

核心思路

暴力做法是枚举所有的切分方案：n-1 个间隙每个都可以切或不切，共 $2^{n-1}$ 种，逐个验证拼接结果是否有序，取块数最多的那个。$n \le 10$ 时勉强能跑，但它完全没抓住结构。

稍好一点的做法是：对每个候选切点 i，检查前缀 arr[0..i] 是否恰好由 ${0, 1, \dots, i}$ 这些值组成——如果是，就可以在这里切一刀。这个判断是对的，但直接实现要么开集合、要么排序，每次判断 $O(i)$，总共 $O(n^2)$。

瓶颈在于「前缀是否恰好是 ${0, \dots, i}$」这个判断被当成了集合比较。观察一下：前缀 arr[0..i] 一共有 i+1 个元素，且这些元素互不相同、都取自 $[0, n-1]$。如果这 i+1 个不同的数的最大值恰好等于 i，那么它们全都落在 $[0, i]$ 这个只有 i+1 个整数的区间里；i+1 个互异的数塞进 i+1 个坑位，只能是一一对应，也就必然恰好是 ${0, 1, \dots, i}$。反过来，若前缀就是 ${0, \dots, i}$，最大值当然是 i。所以——「前缀最大值等于下标」是「前缀恰好是 ${0..i}$」的充要条件，一个标量就替代了整个集合。

这里必须强调「是排列」这个前提在推理中用了两次：一次用来保证元素互异（否则 i+1 个数最大值为 i 也可能有重复而漏掉某些值），一次用来保证值域与下标域一致（否则最大值和下标根本不可比）。

于是维护的不变量是：扫描到下标 i 时，max 恒等于 $\max(arr[0], \dots, arr[i])$；每当 max == i 成立，就说明前缀 arr[0..i] 与后缀 arr[i+1..n-1] 的元素集合完全不交叉（前缀占满 $[0, i]$，后缀占满 $[i+1, n-1]$），因此可以在 i 之后切一刀。

为什么统计所有满足条件的 i 就得到最大块数？因为每个可切点都是独立可用的——在任意一组可切点上同时切开，每一块内部排序后都会落到它应有的值域区间上，拼起来必然整体有序。既然所有可切点都能同时使用，最大块数就等于可切点的总数。注意最后一个位置 i = n-1 必然满足 max == n-1（整个排列的最大值就是 n-1），所以答案至少是 $1$，且不会漏掉最后一块的计数。

解题步骤

初始化 max = 0、chunks = 0。理由：max 会在第一轮立刻被 arr[0] 更新，而数组元素非负，所以用 $0$ 作初值是安全的；chunks 从零开始累加。

从左到右单趟遍历，下标 i 从 $0$ 到 n-1。理由：判定条件只依赖前缀信息，一趟扫描就能把所有前缀依次覆盖，不需要回头也不需要预处理后缀。

每轮先更新 max = Math.max(max, arr[i])。理由：必须先更新再判断，因为「前缀」包含当前元素 arr[i] 本身；先判断再更新会用上一轮的最大值去比对这一轮的下标，判定整体错位一格。

然后判断 if (max == i) chunks++。理由：由前面的推导，这个等式成立当且仅当前缀恰好是 ${0, \dots, i}$，也就是可以在此处切开。不需要额外记录块的起点，因为只关心块的数量。

遍历结束返回 chunks。理由：每个可切点对应一块的结束，最后一个位置必然是可切点，所以可切点数量恰好等于块数，不需要额外加一。

以 arr = [1, 0, 2, 3, 4] 走一遍。i = 0：max = max(0, 1) = 1，1 != 0，不计数——前缀 [1] 里没有 $0$，单独排序后第一位是 $1$，显然不行。i = 1：max = max(1, 0) = 1，1 == 1 成立，chunks = 1——前缀 [1, 0] 恰好是 ${0, 1}$，排序后变成 [0, 1]，可以独立成块。i = 2：max = max(1, 2) = 2，2 == 2，chunks = 2。i = 3：max = 3，相等，chunks = 3。i = 4：max = 4，相等，chunks = 4。返回 $4$，对应切法 [1,0] | [2] | [3] | [4]，与期望一致。

再用反例 arr = [2, 1, 0] 走一遍。i = 0：max = 2，2 != 0。i = 1：max = max(2, 1) = 2，2 != 1——注意这里 max 没有变小，正是「前缀里有个 $2$ 还没等到它的位置」的体现。i = 2：max = 2，2 == 2，chunks = 1。返回 $1$，整个数组只能作为一块，符合直觉。

代码实现

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int max = 0;
        int chunks = 0;

        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            if (max == i) {
                chunks++;
            }
        }

        return chunks;
    }
}

func maxChunksToSorted(arr []int) int {
    maxVal := 0
    chunks := 0

    for i, v := range arr {
        if v > maxVal {
            maxVal = v
        }
        if maxVal == i {
            chunks++
        }
    }

    return chunks
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是数组长度。单趟遍历，每个位置只做一次取最大和一次相等比较，都是常数时间；没有排序、没有嵌套循环、没有回溯。

空间复杂度：$O(1)$。只用了 max 和 chunks 两个整型变量，不开辅助数组也不开栈；虽然本题挂着「单调栈」标签（那是 $768$ 题的解法），但在排列这个前提下退化成了两个标量。

关键点总结

「数组是 $0$ 到 $n-1$ 的排列」是极强的题设，必须主动利用。它同时给出「值域 = 下标域」和「元素互异」两条性质，正是这两条把集合判定压缩成了一个标量比较。看到排列条件却仍去开哈希集合，说明没读透题。

「前缀恰好占满某个区间」这类判定，只要元素互异且个数已知，就等价于「前缀最大值等于区间右端」。计数 + 极值代替集合比较，是一个可迁移到区间覆盖、括号匹配、任务调度等场景的通用压缩技巧。

分块问题里，「块与块之间可否切开」通常是局部可判定的，一旦确认所有可切点互不冲突，最优解就是「能切就切」。这类问题不需要 DP，直接贪心计数即可——但要能说清「为什么所有可切点可以同时生效」。

先更新状态再判断，还是先判断再更新，取决于当前元素算不算在「前缀」里。本题算，所以必须先更新。这个顺序问题在前缀和、前缀最值、哈希配对类题目里反复出现，写之前先明确一次能省掉大量调试。

面试视角：字节考这题的目的是看你能否从「暴力枚举切法」快速跳到「充要条件」。理想的作答是先说暴力 $2^{n-1}$，再说 $O(n^2)$ 的集合判定，最后指出「因为是排列，最大值等于下标就够了」，并给出那句 i+1 个互异数塞进 i+1 个坑位的鸽巢论证。写完主动追问「如果不保证是排列、允许重复怎么办」，自己接上 $768$ 题的答案（用单调栈维护块的最大值，或比较前缀最大值与后缀最小值），这个延伸几乎是必问的。

易错点总结

错误写法：先判断 max == i 再更新 max → 用例 [1, 0] → i = 0 时用初值 max = 0 判断 0 == 0 成立，误计一块；i = 1 时 max 才更新成 $1$，再计一块，返回 $2$，但 [1] | [0] 排序后拼成 [1, 0] 并不有序，正确答案是 $1$。

错误写法：判断条件写成 max == i + 1 → 用例 [0, 1, 2] → 每个位置都不满足，返回 $0$，正确答案是 $3$；下标从 $0$ 开始且值也从 $0$ 开始，两者直接相等，不需要偏移。

错误写法：判断条件写成 max <= i → 用例 [0, 1, 2] → 结果恰好正确，但换成任何 max 短暂大于 i 的输入本质上等价（max 恒不小于 i 的下界只在排列下成立），一旦题目放宽到非排列输入，<= 会在有重复元素时误判出多余切点。

错误写法：返回 chunks + 1，以为最后一块没被计入 → 用例 [4, 3, 2, 1, 0] → 最后一个位置 max = 4 == 4 已经计过一次，再加一返回 $2$，正确答案是 $1$。

错误写法：用后缀最小值来判断，写成「若 arr[i] < 后缀最小值 则切」但把后缀定义成包含 i 自身 → 用例 [1, 0, 2] → i = 0 时后缀含自身最小值是 $0$，1 < 0 不成立正确；但 i = 2 时后缀就是自己，条件恒不成立，最后一块被漏掉，返回 $2$ 而不是 $3$。

错误写法：max 初值设成 Integer.MIN_VALUE 之外还把 chunks 初值设成 $1$ → 用例 [0] → i = 0 时条件成立 chunks 变成 $2$，正确答案是 $1$；本题所有块都由「条件成立」计数，初值必须是 $0$。

错误写法：每轮重新对前缀做一次排序或构造集合来验证是否为 ${0..i}$ → 用例长度 $10$ 的数组 → 结果正确但复杂度是 $O(n^2 \log n)$，且完全没有体现「排列」这个题设，面试中会被要求重写。

错误写法：Go 里用 for i, v := range arr 但比较时误用 v == i 而不是 maxVal == i → 用例 [1, 0, 2] → i = 0 时 v = 1 不等，i = 1 时 v = 0 不等，i = 2 时 v = 2 相等，返回 $1$，正确答案是 $2$；判定必须基于前缀最大值而不是当前元素。

错误写法：认为「块必须等长」或「块的起点要显式记录」，于是维护一个 start 变量并在切块时做子数组拷贝 → 用例任意输入 → 逻辑上不错但引入了 $O(n)$ 额外空间和大量无用代码；题目只问数量，任何构造块内容的动作都是多余的。

错误写法：把 max 的更新写成 max = arr[i]（直接赋值而非取最大）→ 用例 [2, 1, 0] → i = 1 时 max 被降成 $1$，1 == 1 成立误计一块；i = 2 时 max 降成 $0$，0 != 2 不计，返回 $1$ 虽然侥幸对，但换成 [2, 0, 1] 时 i = 1 处 max = 0 不等、i = 2 处 max = 1 不等，返回 $0$，正确答案是 $1$。

相似题目

题目	难度	考察点
768. 最多能完成排序的块 II	困难	去掉排列前提、允许重复与任意值域，必须改用单调栈或前缀最大对后缀最小
581. 最短无序连续子数组	中等	同样用前缀最大与后缀最小定位边界，但求的是最短乱序区间而非切块数
31. 下一个排列	中等	也依赖「从右往左的单调性」找到第一个失序位置，考察原地重排的完整流程
739. 每日温度	中等	单调栈的标准入门题，用来对照本题标签中「单调栈」在放宽条件后的真正用法
84. 柱状图中最大的矩形	困难	单调栈的进阶应用，栈中维护的是可扩展区间而非块最大值