題目
給你一個(gè)整數(shù)數(shù)組 arr 。
將 arr 分割成若干 塊 ，并將這些塊分別進(jìn)行排序竹伸。之后再連接起來，使得連接的結(jié)果和按升序排序后的原數(shù)組相同簇宽。
返回能將數(shù)組分成的最多塊數(shù)勋篓？
示例 1：
輸入：arr = [5,4,3,2,1]
輸出：1
解釋：
將數(shù)組分成2塊或者更多塊，都無法得到所需的結(jié)果魏割。
例如譬嚣，分成 [5, 4], [3, 2, 1] 的結(jié)果是 [4, 5, 1, 2, 3]，這不是有序的數(shù)組钞它。
示例 2：
輸入：arr = [2,1,3,4,4]
輸出：4
解釋：
可以把它分成兩塊拜银，例如 [2, 1], [3, 4, 4]。
然而遭垛，分成 [2, 1], [3], [4], [4] 可以得到最多的塊數(shù)尼桶。
提示：
1 <= arr.length <= 2000
0 <= arr[i] <= 108
解題思路
計(jì)數(shù)排序
class Solution768 {
func maxChunksToSorted(_ arr: [Int]) -> Int {
// 定義一個(gè)變量 ans，用于記錄最終的答案
var ans = 0
var countA = [Int: Int]()
var countB = [Int: Int]()
// 遍歷 arr 和 arr.sorted()耻卡，將它們的每個(gè)元素合并成一個(gè)元組 (a, b)
for (a, b) in zip(arr, arr.sorted()) {
// 在 countA 中增加 a 出現(xiàn)的次數(shù)
countA[a, default: 0] += 1
// 在 countB 中增加 b 出現(xiàn)的次數(shù)
countB[b, default: 0] += 1
// 如果 countA 和 countB 相等疯汁，那么說明 arr 的前 i 個(gè)元素可以分成一個(gè) 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);
}
}
