0769-最多能完成排序的块

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

给定一个长度为 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 中每个元素都 不同

方法一：贪心

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

  • 定理一：对于某个块 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 一种分割方案为：[a_0, a_{i_1}], [a_{i_1+1}, a_{i_2}], \ldots, [a_{i_m+1}, a_{n-1}]，那么由定理一可知 [a_0, a_{i_1}], [a_0, a_{i_2}], \ldots, [a_0, a_{n-1}] 分别排序后与原数组排序后的结果一致。反之如果 [a_0, a_{i_1}], [a_0, a_{i_2}], \ldots, [a_0, a_{n-1}] 分别排序后与原数组排序后的结果一致，那么由定理二可知 [a_0, a_{i_1}], [a_{i_1+1}, a_{i_2}], \ldots, [a_{i_m+1}, a_{n-1}] 是数组 arr 一种分割块方案。

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

[sol1-Python3]
1
2
3
4
5
6
7
class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        ans = mx = 0
        for i, x in enumerate(arr):
            mx = max(mx, x)
            ans += mx == i
        return ans
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int m = 0, res = 0;
        for (int i = 0; i < arr.size(); i++) {
            m = max(m, arr[i]);
            if (m == i) {
                res++;
            }
        }
        return res;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxChunksToSorted(int[] arr) {
        int m = 0, res = 0;
        for (int i = 0; i < arr.length; i++) {
            m = Math.max(m, arr[i]);
            if (m == i) {
                res++;
            }
        }
        return res;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int MaxChunksToSorted(int[] arr) {
        int m = 0, res = 0;
        for (int i = 0; i < arr.Length; i++) {
            m = Math.Max(m, arr[i]);
            if (m == i) {
                res++;
            }
        }
        return res;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int maxChunksToSorted(int* arr, int arrSize) {
    int m = 0, res = 0;
    for (int i = 0; i < arrSize; i++) {
        m = MAX(m, arr[i]);
        if (m == i) {
            res++;
        }
    }
    return res;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
func maxChunksToSorted(arr []int) (ans int) {
    mx := 0
    for i, x := range arr {
        if x > mx {
            mx = x
        }
        if mx == i {
            ans++
        }
    }
    return
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
var maxChunksToSorted = function(arr) {
    let m = 0, res = 0;
    for (let i = 0; i < arr.length; i++) {
        m = Math.max(m, arr[i]);
        if (m === i) {
            res++;
        }
    }
    return res;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 arr 的长度。

  • 空间复杂度：O(1)。

 Comments
On this page
0769-最多能完成排序的块