【刷题日记】768. 最多能完成排序的块 II

本次刷题日记的第 92 篇，力扣题为：768. 最多能完成排序的块 II

一、题目描述：

继续干最多能完成排序的快 II ， 看看进阶版的是什么样的需求

二、这道题考察了什么思想？你的思路是什么？

进阶版的最多能完成排序的块 II ， 是够会促使我们改变上次做题的方式和思路呢

这一次的题目变动情况是这样的：

• 题目中的数组长度最大限度变成了 2000，数组中的数据最大元素变成 10^8，再也不是 0 到 n-1 了
• 题目给出的 arr 数组中的元素，并不是根据 arr 长度来的了，数组里面的元素数值不可预测，只知道是最大为 10^8
• 要求我们还是继续拆分数组，拆分成最大的块，并且将这些块，各自排序，拼接成升序之后的原数组

分析

根据本次进阶的排序块问题，我们也许不能直接用 arr 的数组索引来做文章了，因为 arr 里面的元素索引和具体对应的数值已经没有啥直接关系了，既然继续沿用索引的方式行不通，那么我们从其他方面找解决方式

咱们思考的方向可以是这样的：

• 第一，无论拆分成多少块，各自排序拼接之后，都需要是和原数组升序之后的结果一致
• 第二，无论如何拆分块以及其各自排序，对于数组中的数据，我们是一点也不能去修改的，原来有多少个 1 ，那么拆分数组后，总的来说，还是多少个 1

这个时候，既然我们其实还是需要和原数组的升序结果做对比的话，再加上我们不能使用索引做文章，那么我们是否可以使用每个块的数字出现频次做文章呢？

例如我们可以看到示例 2 中

Arr = [2, 1, 3, 4, 4]

这个时候，除了眼睛可以一眼看出可以最多拆分多少块外，我们还需要有明确的程序和逻辑

我们其实可以看到 ，咱们是可以拆分成 4 个块的，再仔细看每一个块的原数组内容和排序后的数据内容

实际上我们是可以看出，对于原数组中一个单独的块中，当前块中的数字个数，类型，出现的频次，与升序后的原数组对应的块中的 数字个数，类型，出现的频次 完全一致，只是出现快中的索引位置不一样而已，这也是为什么最开始我就说到，咱们就不要打索引的注意了

那么，这个时候咱们做题分析的话，

• 第一，需要一个对原数组升序之后的结果来进行帮助比较和计算，定义数组为 help
• 第二，需要一个 map 来记录某一个块中，原数组出现过就 +1，help 数组也出现过就 -1，对于 map 来说，一加一减就还原了，那么遍历原数组 arr 过程中，如果有出现咱们比较数字频次之后，map 仍然长度为 0，则咱们就需要拆分块了
• 例如上述案例，遍历到arr的第二个元素的时候，出现的 2，1 与 排序数组的前两个元素 1,2 出现的频次一样，这个时候，就进行拆分块

至此，剩下就是按照上述思路进行撸代码吧

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

• 需要关注，咱们需要先对 arr 数组进行排序，得到 help
• 遍历 arr，使用 cntMap 来标记在遍历过程数字出现的频次，arr 中出现就 +1，相应的 help 中出现就 -1，逻辑处理完毕后，校验 cntMap 长度是否为 0，若是，这满足我们拆分的条件，则拆分即可
• 最终返回最大拆分的次数

编码如下：

func maxChunksToSorted(arr []int) int {
    cntMap := map[int]int{}
    help := append([]int{}, arr...)
    sort.Ints(help)
    var res int
    for index, aNum := range arr {
        // 表示 aNum 在 arr 中出现频次+1
        cntMap[aNum]++
        if cntMap[aNum] == 0{
            delete(cntMap, aNum)
        }
        // 在来看 help 中对一个位置数值的频次
        cntMap[help[index]]--
        if cntMap[help[index]] == 0 {
            delete(cntMap, help[index])
        }
        // 最后校验我们的 map 中没有数据，说明目前为止，遍历的数据的频次 arr 和 help 对应数据的频次一致
        if len(cntMap) == 0 {
            res++
        }
    }
    return res
}

四、总结：

本题的处理方式使用了 golang 自带库中的快速排序，因而时间复杂度是 O(nlogn) ，空间复杂度比较明确，我们开辟了一个 help 切片，数据长度和题目给出的 arr 一样，则为 空间复杂度为O(n)

原题地址：768. 最多能完成排序的块 II

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~