难度: Medium
给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
我们将 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]
提示:
n == arr.length1 <= n <= 100 <= arr[i] < narr 中每个元素都 不同运行时间: 22 ms
内存: 16.0 MB
class Solution:
def maxChunksToSorted(self, arr: List[int]) -> int:
chunks, cur_max = 0, 0
for i in range(len(arr)):
cur_max = max(cur_max, arr[i])
chunks += cur_max == i
return chunks
题解的思路是迭代数组并维护当前遍历到的元素的最大值 cur_max。对于每个位置 i，如果 cur_max 等于 i，这意味着从 0 到 i 的元素正好是 0 到 i 的所有整数，因此可以形成一个块。每当这种情况发生时，块的计数器 chunks 就增加 1。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def maxChunksToSorted(self, arr: List[int]) -> int:
chunks, cur_max = 0, 0 # 初始化块计数器和当前最大值
for i in range(len(arr)):
cur_max = max(cur_max, arr[i]) # 更新当前最大值
chunks += cur_max == i # 如果当前最大值等于索引，则增加块计数器
return chunks # 返回块的总数
当`cur_max == i`时，说明从数组的起始到当前位置i的最大值刚好是i。由于数组元素是从0开始连续的整数，不考虑重复元素的情况下，如果最大值是i，那么从0到i必须包含了所有小于等于i的整数，这样才能保证这部分是完整的并且可以独立于数组的其他部分进行排序。因此，每当检测到`cur_max == i`时，可以确信这一部分数组可以形成一个独立的块。
如果数组中存在重复元素，那么原算法将不再适用。这是因为重复元素会打破从0到i的索引与值一一对应的关系，导致即使`cur_max == i`也不能保证这之前的所有整数都已经出现。例如，数组[0, 1, 1, 2]中，尽管在索引2时`cur_max == 2`，但0到2的块并不能独立排序，因为它缺少数字0或1的另一个副本。因此，算法需要调整以适应包含重复元素的情况。
在这个算法中，更新当前最大值`cur_max`并用它来确定是否可以形成一个块，是因为这个最大值可以帮助我们了解从数组开始到当前位置的元素范围。如果当前的最大值恰好等于当前的索引，那么意味着从0到该索引的所有整数都至少已经出现过一次，从而可以形成一个可以独立排序的块。这种方法依赖于数组元素与其索引位置之间的这种特定关系，是判断能否形成块的一个简单而有效的条件。
在数组已经是排序状态（例如[0, 1, 2, 3]）的情况下，该算法表现良好，因为每个元素的索引与其值相等，`cur_max`将会在每个位置都等于索引，从而每个元素都可以形成一个块，块的数量等于数组的长度。相反，在完全逆序的情况下（例如[3, 2, 1, 0]），`cur_max`始终为数组的最大元素，直到遍历到最后一个元素时`cur_max`才等于索引，此时只能形成一个块。因此，该算法在这两种极端情况下都能正确处理，但块的数量会有很大差异。