leetcode769 最多能完成排序的块_将 a 分成 [1,0],[4,3,2] 两部分分别排序,可以让整个数组变得有序。但分成更多块-CSDN博客

本文链接：https://blog.csdn.net/Hello_R/article/details/120068551

该篇博客讨论了一道编程题目，涉及数组的排序与分块。内容解析了如何确定一个数组最多能被分成多少块，使得每块排序后整个数组按升序排列。通过遍历数组，利用最大值的概念来划分块，最终得出解决方案。示例展示了具体的操作过程和代码实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

数组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]的一种排列。

思路：本题的难点在于理解题意，一旦理解了，问题也就迎刃而解了。要知道每个数最后排序时都应该处于等于其数值的位置上，因此一旦遇到大于自己位置的数时，接下来一段区域内就都只能划分为一块，直到这个数达到其所应在的位置时。而每一块中是由最大的数决定划分的区域，因此可以设定一个max值，起初为0，一旦遇到更大值，便进行更新，直到某个最大值达到了它应在的位置，将max清空，将块计数加一，这样遍历到数组结尾即为所求。

代码：

class Solution {
    public int maxChunksToSorted(int[] arr) {
 int num = 0;
        int max = 0;
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if(arr[i] > max)
            {
                max = arr[i];
            }
            if(i == max)
            {
                num++;
                max = 0;
            }
        }
        return num;
    }
}