LeetCode 769. 最多能完成排序的块
题目描述
题意分析
数组恰好包含
0到n - 1，每个数出现一次。把它切成若干连续块，只允许在各块内部排序，块与块的先后顺序不变，要求拼接结果与整个数组排序后的结果一致，并让块数最多。完全排好序后，下标
i处的值就是i。因此要判断能否在i后面切开，只需检查前i + 1个位置是否已经收齐最终属于这个前缀的全部值。
解法：前缀最大值
核心思路
[!blue]
用
max维护arr[0..i]的最大值。当前前缀有i + 1个互不相同的非负整数；如果max == i，所有值都来自只有i + 1个数的集合{0, 1, ..., i}，所以这个集合必然已经被完整收齐。前缀内部排序后就能放到正确位置，后面的值都大于i，在这里切开不会妨碍全局有序。反过来，如果这里能够切开，前缀中的数就无法再移动到后缀中，必须恰好是
0到i，最大值也就一定等于i。所以max == i是合法切点的充要条件，而不只是一个足够条件。max < i在本题中不可能出现，因为i + 1个不同非负数无法都塞进更小的值域。所有合法切点还可以同时选取：两个相邻切点对应的前缀分别收齐两个连续值域，它们的差集正好就是中间那一块应该包含的值。把这一块单独排序，仍能占据正确的位置。因此每遇到一个合法切点就增加一块，既不会破坏其他切点，又取得了所有可能的切点，块数最多。
遍历时先把当前元素计入
max，再检查是否等于当前下标。max始终表示整个前缀，不必在切块后清零。最后一个位置的前缀包含全部排列，最大值一定是n - 1，会自然结算最后一块。
解题步骤
- 维护包含当前值的前缀最大值。
- 最大值等于当前下标时，块数加一。
- 遍历结束直接返回，不额外加块。
数组只有一个元素时返回一块；原数组已经升序时，每个位置都可以成为一块。这个判定依赖“元素互异且值域恰好为
0到n - 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)$，一次扫描。
- 空间复杂度：$O(1)$，前缀最大值与计数。
关键点总结
[!green]
- 判定同时依赖值域与互异性，不能直接用于任意含重复数组。
- 判断的是整个前缀最大值，不是当前值。
易错点总结
[!yellow]
- 先判定再更新，会把当前更大值漏出前缀。
- 最后再加一，会重复计算已经结算的末块。
- 直接把最大值改成当前值，会遗忘前面尚未归位的大元素。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 768. 最多能完成排序的块 II | 困难 | 去掉排列前提后，下标与数值不再直接对应，需要更一般的前后缀边界或多重集合判定。 |
| 915. 分割数组 | 中等 | 同样要求左段最大值不大于右段最小值，原题只找一个最早分割，本题找尽可能多的切点。 |