题目
给你一个整数数组 arr 。
将 arr 分割成若干 块 ，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
返回能将数组分成的最多块数？
示例 1：
输入：arr = [5,4,3,2,1] 输出：1 解释： 将数组分成2块或者更多块，都无法得到所需的结果。 例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。 示例 2：
输入：arr = [2,1,3,4,4] 输出：4 解释： 可以把它分成两块，例如 [2, 1], [3, 4, 4]。 然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。
提示：
1 <= arr.length <= 2000 0 <= arr[i] <= 108
解题思路
计数排序
代码语言：javascript复制class Solution768 {
func maxChunksToSorted(_ arr: [Int]) -> Int {
// 定义一个变量 ans，用于记录最终的答案
var ans = 0
var countA = [Int: Int]()
var countB = [Int: Int]()
// 遍历 arr 和 arr.sorted()，将它们的每个元素合并成一个元组 (a, b)
for (a, b) in zip(arr, arr.sorted()) {
// 在 countA 中增加 a 出现的次数
countA[a, default: 0] = 1
// 在 countB 中增加 b 出现的次数
countB[b, default: 0] = 1
// 如果 countA 和 countB 相等，那么说明 arr 的前 i 个元素可以分成一个 chunk，并将 ans 加 1
print(countA,countB)
if countA == countB {
ans = 1
}
}
// 返回最终的答案
return ans
}
func test() {
// var arr = [5,4,3,2,1]
var arr = [2,1,3,4,4]
let ret = maxChunksToSorted(arr);
print(ret);
}
}
