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

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

一、题目描述：

买股票的三连刷我们写完了，今天来刷 最多能完成排序的块

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

最多能排序的块，不知 xdm 看上去是否感觉和买股票有点相似，或者说和上一次的用户分组也非常相似，都是需要我们拆分数组，只不过题目要求和条件不一样罢了，那么我们的实现方式又有何不同呢，来看看

• 题目给出一个长度为 n 的数组，数组中的元素是唯一的，且是 0 到 n-1 的序列，顺序是被打乱的
• 这个时候，题目要求我们去拆分数组，尽可能的拆分成最多的块，唯一要求就是，这些拆分的块排序后，按照顺序拼接起来，与源数组排序后（升序）的结果是一致的

分析

看了上面的描述和转义，其实我们对题目的要求还是相当明确的，可是我们需要去实现这个需求呢

第一，我们要把握住拆分最多的块

第二，我要需要注意原数组，和拆分后的块，是需要升序排序后对比的

第三，我们要清晰的知道数组中的数字是不会重复的，且一定是 0 到 n-1

也就是说，如果 n 等于 8 ， 那么 0 到 7 这 8 个数字一定在数组中，只是顺序被打乱的了而已

我们可以来看看 0 到 7 如果排序后是什么样子的

其实通过上述表格我们清晰的可以看到，实际上数组的索引和数组的值是一一对应的，那么这个时候，如果 0 到 7 这个串数字是被打乱的话，我们可以如何来去拆分后，拼接成升序数组呢

举个栗子：

这个时候，通过这个小案例，其实，我们一眼就能看出需要如何拆分，例如这样

明确是拆分成 3 份的，当然，如果对于数据量大，那肯定就不能是一眼看出，必然是需要遵循某种逻辑和算法的

仔细看第 2 块，实际上我们就是在遍历数组的时候，如果当前索引 例如 1，不等于当前值例如 3，那么就需要记录下来当前的值 例如 maxNum = 3 ，遍历过程中，如果有更大的值但是和索引不相等的情况，那么就更新 maxNum，直到我们遍历到 索引与 maxNum 相等时候，那么这个时候就该拆分素组了，例如第 2 块，就是遍历到 索引为 3 ，maxNum 为 3 的时候，我们的程序就知道需要拆分数组了

当然第 3 块也是同样的道理

这个时候，剩下的就是开心的撸代码了，一次撸代码开心一次，一直撸代码，一直开心

三、编码

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

• 我们需要重点关注区间内 maxNum 是否和当前索引相当，若相等，则拆分

编码如下：

func maxChunksToSorted(arr []int) int {
    var res int
    var maxNum int
    // 直接找到数组中的目前为止最大值，是否和目前索引对的上，若对的上就分区间
    for i:=0; i<len(arr); i++ {  
        maxNum = max(arr[i], maxNum)
        if i == maxNum {
            res++
         }
    }
    return res
}
func max(a, b int) int {
    if a>b {
        return a
    }
    return b
}

四、总结：

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

本题的实现方式，完成了一次遍历 arr 数组，因此时间复杂度是 O(n)，空间复杂度为 O(1) ，咱们未印日额外的空间消耗

欢迎点赞，关注，收藏

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

好了，本次就到这里

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

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