本次刷题日记的第 91 篇，力扣题为：769. 最多能完成排序的块
一、题目描述：
买股票的三连刷我们写完了，今天来刷 最多能完成排序的块
二、这道题考察了什么思想？你的思路是什么？
最多能排序的块，不知 xdm 看上去是否感觉和买股票有点相似，或者说和上一次的用户分组也非常相似，都是需要我们拆分数组，只不过题目要求和条件不一样罢了，那么我们的实现方式又有何不同呢，来看看
- 题目给出一个长度为 n 的数组，数组中的元素是唯一的，且是 0 到 n-1 的序列，顺序是被打乱的
- 这个时候，题目要求我们去拆分数组，尽可能的拆分成最多的块，唯一要求就是，这些拆分的块排序后，按照顺序拼接起来，与源数组排序后（升序）的结果是一致的
分析
看了上面的描述和转义，其实我们对题目的要求还是相当明确的，可是我们需要去实现这个需求呢
第一，我们要把握住拆分最多的块
第二，我要需要注意原数组，和拆分后的块，是需要升序排序后对比的
第三，我们要清晰的知道数组中的数字是不会重复的，且一定是 0 到 n-1
也就是说，如果 n 等于 8 ， 那么 0 到 7 这 8 个数字一定在数组中，只是顺序被打乱的了而已
我们可以来看看 0 到 7 如果排序后是什么样子的
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 数值 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
其实通过上述表格我们清晰的可以看到，实际上数组的索引和数组的值是一一对应的，那么这个时候，如果 0 到 7 这个串数字是被打乱的话，我们可以如何来去拆分后，拼接成升序数组呢
举个栗子：
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 数值 | 0 | 3 | 2 | 1 | 7 | 5 | 6 | 4 |
这个时候，通过这个小案例，其实，我们一眼就能看出需要如何拆分，例如这样
明确是拆分成 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) ，咱们未印日额外的空间消耗
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
