LeetCode 769.最多能完成排序的块(中等)

题目描述:

数组 ​​arr​​​ 是 ​​[0, 1, ..., arr.length - 1]​​ 的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。我们最多能将数组分成多少块？

示例 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] 可以得到最多的块数。

注意:

• ​​arr​​​ 的长度在 ​​[1, 10]​​ 之间。
• ​​arr[i]​​​ 是 ​​[0, 1, ..., arr.length - 1]​​ 的一种排列。

题目分析:

这道题也是一道找规律的题目，特别注意下标值。因为题目给定数组 ​​arr​​​ 是 ​​[0, 1, ..., arr.length - 1]​​​ 的一种排列，所以我们可以从左往右检查局部序列，比如局部序列 ​​[0, 1, ..., n]​​​ ，看看局部序列中最大的数是不是 ​​n​​​ ，如果是就能进行一次分割，否则不能分割。也就是说，当遍历到第 ​​n​​​ 个位置时，如果可以切成块，那满足前 ​​n + 1​​​ 个元素的最大值一定等于 ​​n​​​ 。否则一定有比 ​​n​​ 还要小的数组值被强制划分到后面的块去了，这样排序出来的各个块连起来不满足全部升序。因此，我们可以从左往右遍历数组，获取当前局部序列的最大值，当当前最大值等于下标值时，可以进行一次分割。

题解:

执行用时: 0 ms

内存消耗: 35.5 MB

class Solution {
    public int maxChunksToSorted(int[] arr) {
        // 定义 分割次数 和 当前最大值
        int count = 0, max = 0;
        // 遍历整个数组
        for (int i = 0; i < arr.length; ++i) {
            // 获取当前最大值
            max = Math.max(max, arr[i]);
            // 如果当前最大值与下标值相等
            if (max == i) {
                // 分割次数加一
                ++count;
            }
        }
        // 返回最大分割次数
        return count;
    }
}

题目来源:力扣(LeetCode)