景真

外观

最多能完成排序的块

约 1636 字大约 5 分钟

贪心抽屉原理

2025-03-02

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] 可以得到最多的块数。
对每个块单独排序后，结果为 [0, 1], [2], [3], [4]

提示:

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

贪心，抽屉原理

类似跳跃游戏，元素值与索引之间的对应。

只需要找到 [a0,ai1],[a0,ai2],…,[a0,an−1]\left[a_0, a_{i_1}\right],\left[a_0, a_{i_2}\right], \ldots,\left[a_0, a_{n-1}\right] 的最大数目， 就能找到最大分割块数目。因为数组 arr⁡\operatorname{arr} 的元素在区间 [0,n−1][0, n-1] 之间且互不相同， 所以数组排序后有 arr⁡[i]=i\operatorname{arr}[i]=i 。 如果数组 arr⁡\operatorname{arr} 的某个长为 i+1i+1 的前缀块 [a0,ai]\left[a_0, a_i\right] 的最大值等于 ii ， 那么说明它排序后与原数组排序后的结果一致。统计这些前缀块的数目，就可以得到最大分割块数目。 或者考虑到数组长度为n，而且数组元素位于区间[0, n-1]且不重复，那么数组排好序后，每个值和下标恰好是相等的； 所以，从左到右遍历数组，并且分别对值和下标累加求和，只要两个和相等，就切出一个块。

根据题意我们可以得到以下两个定理：

  • 定理一：对于某个块 A，它由块 B 和块 C 组成，即 A=B+C。如果块 B 和块 C 分别排序后都与原数组排序后的结果一致，那么块 A 排序后与原数组排序后的结果一致。

证明：因为块 B 和块 C 分别排序后都与原数组排序后的结果一致，所以块 B 的元素和块 C 的元素的并集为原数组排序后在对应区间的所有元素。而 A=B+C，因此将块 A 排序后与原数组排序后的结果一致。

  • 定理二：对于某个块 A，它由块 B 和块 C 组成，即 A=B+C。如果块 A 和块 B 分别排序后都与原数组排序后的结果一致，那么块 C 排序后与原数组排序后的结果一致。

证明：如果块 C 排序后与原数组排序后的结果不一致，那么块 B 的元素和块 C 的元素的并集不等同于原数组排序后在对应区间的所有元素。而块 A 排序后与原数组排序后的结果一致，说明块 A 的元素等同于原数组排序后在对应区间的所有元素。这与块 A 的元素由块 B 的元素和 块 C 的元素组成矛盾，因此块 C 排序后与原数组排序后的结果一致。

假设数组 arr⁡\operatorname{arr} 一种分割方案为：[a0,ai1],[ai1+1,ai2],…,[aim+1,an−1]\left[a_0, a_{i_1}\right],\left[a_{i_1+1}, a_{i_2}\right], \ldots,\left[a_{i_m+1}, a_{n-1}\right]，那么由定理一可知 [a0,ai1],[a0,ai2],…,[a0,an−1]\left[a_0, a_{i_1}\right],\left[a_0, a_{i_2}\right], \ldots,\left[a_0, a_{n-1}\right] 分别排序后与原数组排序后的结果一致。反之如果 [a0,ai1],[a0,ai2],…,[a0,an−1]\left[a_0, a_{i_1}\right],\left[a_0, a_{i_2}\right], \ldots,\left[a_0, a_{n-1}\right] 分别排序后与原数组排序后的结果一致，那么由定理二可知 [a0,ai1],[ai1+1,ai2],…,[aim+1,an−1]\left[a_0, a_{i_1}\right],\left[a_{i_1+1}, a_{i_2}\right], \ldots,\left[a_{i_m+1}, a_{n-1}\right] 是数组 arr⁡\operatorname{arr} 一种分割块方案。

因此我们只需要找到 [a0,ai1],[a0,ai2],…,[a0,an−1]\left[a_0, a_{i_1}\right],\left[a_0, a_{i_2}\right], \ldots,\left[a_0, a_{n-1}\right] 的最大数目，就能找到最大分割块数目。因为数组 arr⁡\operatorname{arr} 的元素在区间 [0,n−1][0, n-1] 之间且互不相同，所以数组排序后有 arr⁡[i]=i\operatorname{arr}[i]=i 。如果数组 arr⁡\operatorname{arr} 的某个长为 i+1i+1 的前缀块 [a0,ai]\left[a_0, a_i\right] 的最大值等于 ii ，那么说明它排序后与原数组排序后的结果一致。统计这些前缀块的数目，就可以得到最大分割块数目。

当遍历到数组的某个位置 i 时，如果从起点到 i 的所有元素中的最大值恰好等于 i，这意味着从起点到 i 的这部分数组中的所有元素都正好可以构成一个排序后与整体排序相同的子数组。和跳跃游戏、数组中重复的元素有点像。

5个数里最大值是5，这五个数互不相等且都为正数，则剩下四个数一定是1，2，3，4。本质上是抽屉原理。

重点：

  1. 每个元素都不同。
  2. 元素的取值范围都是[0,n-1]。
class Solution {
    public int maxChunksToSorted(int[] arr) {
        int m = 0; // 用于记录当前块中最大的值
        int res = 0; // 用于记录可以分成的块数

        // 遍历数组中的每个元素
        for (int i = 0; i < arr.length; i++) {
            // 不断记录或更新当前块中的最大值
            m = Math.max(m, arr[i]);
            
            // 如果当前块中的最大值等于当前索引，则可以将当前块分开
            // 最大值m到0一共有m+1个数，从0到当前索引i一共有i+1个数
            // m==i说明[0,m]=[0,i]，这说明在当前i+1个数里，最大值是i，最小值是0，题目说每个数都不一样，所以这个区间中的数一定是0,1,...,i。抽屉原理。
            if (m == i) {
                res++; // 增加块数。不用重置最大值为0，因为下一个数一定大于当前最大值。
            }
        }
        
        return res; // 返回最多可以分成的块数
    }
}
  • 时间复杂度：O(n)，其中 n 是数组 arr 的长度。
  • 空间复杂度：O(1)。