769. 最多能完成排序的块

题目描述：

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。

我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。

返回数组能分成的最多块数量。

示例 1:
输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。

示例 2:
输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
提示:

• n == arr.length
• 1 <= n <= 10
• 0 <= arr[i] < n
• arr 中每个元素都 不同

---

解题分析及思路：

需要将目标数据进行分割，将其分成若干个小数组，并且每个小数组按照升序排序后进行拼接成一个新的数组，该数组与目标数组升序排序后结果一致。

那么重点在于如何进行更多次数的分割。

遍历数组，依次找到未遍历的数中的最小数，也就是每次分割后的第一个值的下标，找到即分割一次。

例如：1,0,2,3,4

最开始从下标0开始，那么需要找到0这个数后进行分割，即1,0为一块，分割后需要找到2的数，恰好数2对应的下标就是2,则再次进行分割。以此类推。

最终，得到的块为1,0,2,3,4。

在此过程中，只需一个变量保存最开始的数的下标，并且在每次分割后更新该下标的值即可。分割时，结果进行加一。

复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:1.8 MB,击败了75.41% 的Go用户