---

0769. 最多能完成排序的块

• 标签：栈、贪心、数组、排序、单调栈
• 难度：中等

题目链接

• 0769. 最多能完成排序的块 - 力扣

题目大意

描述：

给定一个长度为 $n$ 的整数数组 $arr$，它表示在 $[0, n - 1]$ 范围内的整数的排列。

我们将 $arr$ 分割成若干块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。

要求：

返回数组能分成的最多块数量。

说明：

• $n == arr.length$。
• $1 \le n \le 10$。
• $0 \le arr[i] \lt n$。
• $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] 可以得到最多的块数。
对每个块单独排序后，结果为 [0, 1], [2], [3], [4]

解题思路

思路 1：贪心算法

这道题是 0768 题的简化版本，数组元素是 $[0, n-1]$ 的排列。

核心观察：

• 由于数组是 $[0, n-1]$ 的排列，如果前 $i+1$ 个元素的最大值等于 $i$，说明前 $i+1$ 个元素恰好是 $[0, i]$。
• 此时可以在位置 $i$ 处分割，因为前面的元素排序后不会影响后面的元素。

解题步骤：

1. 从左到右遍历数组，维护当前的最大值 $max\_val$。
2. 如果在位置 $i$ 处，$max\_val = i$，说明前 $i+1$ 个元素恰好是 $[0, i]$，可以分割。
3. 统计所有可以分割的位置数量。

思路 1：代码

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        chunks = 0
        max_val = 0
        
        for i in range(len(arr)):
            max_val = max(max_val, arr[i])
            # 如果当前最大值等于索引，说明前面的元素恰好是 [0, i]
            if max_val == i:
                chunks += 1
        
        return chunks

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $arr$ 的长度。需要遍历数组一次。
• 空间复杂度：$O(1)$。只使用了常数个额外变量。