LeetCode 769. Max Chunks To Make
image.png
问题描述
给定一个数组 arr，它是 [0, 1, ..., arr.lenth - 1] 的排列。我们将数组分为一个个区块，并单独排序，最后将每个区块连接起来，要求是有序的。
我们最多可将数组分为多少个区块？
栗 1：
输入：arr = [4,3,2,1,0]
输出：1
解释：
最多只能划分为 1 个，因为分成多个区块后，连接后无法有序。
栗 2：
输入：arr = [1,0,2,3,4]
输出：4
解释：
可将其划分为 [1, 0], [2], [3], [4] 4 个区块。
注意：
-
arr的长度为[1, 10]。 -
arr[i]是[0, 1, ..., arr.lenth - 1]的任意排列。
解题思路
解法 1
这是我的解法。
思路分析
首先我们需要考虑的是，在什么情况下可以划分为独立的区块？
单区块
假设已有区块 [2, 1]，对于不同的数字，会有不同的处理。
- 对于
0来说，0 < 2，肯定是需要划分到一个区块中，即[2, 1, 0]。因为0单独成块后，无法有序。 - 对于
3来说，3 > 2，可以单独成为一个区块。
从上可以看出，只要待处理的数字小于区块的最大值，就需要合并到一个区块中，否则可独立。
多区块
但区块可能有多个，且前面区块的最大值小于后面区块。因此在比较时，需从前往后与每个区块的最大值进行比较。
- 如果比某个区块最大值小，则需合并到该区块中，其后的区块也连同合并。因为区块是按顺序划分的。
- 如果比所有区块最大值都大，则可单独成块。
举个例子，假设已有区块 c1 = [1, 2, 3, 0], c2 = [6], c3 = [8]。
当处理 5 时，从前往后比，它比 c2 的最大值要小，因此需合并到 c2，且连同 c2、c3 一起合并，则最终区块变为： c1 = [1, 2, 3, 0], c2 = [6, 8, 5]。
当处理 10 时，它比所有区块的最大值都大，因此可单独成块。最终区块变为： c1 = [1, 2, 3, 0], c2 = [6], c3 = [8], c4 = [10]。
思路总结
所以，最终的思路为：
- 使用数组记录每个区块的最大值。
- 逐个对数字进行处理，合并或者添加区块，并更新区块最大值。
- 数组的长度即为最终区块个数。
代码实现
js 代码实现如下：
var maxChunksToSorted = function (arr) {
if (arr && arr.length > 0) {
let maxNum = arr[0];
// 存储每一段的最大值
let chunksMaxNum = [arr[0]];
var i = 1;
while (i <= arr.length - 1) {
let flag = false;
// 逐个与 chunksMaxNum 进行比较
let j = 0;
while (j < chunksMaxNum.length) {
if (arr[i] < chunksMaxNum[j]) {
// 标记为已处理
flag = true;
// 从 j 起，需要合并
// 最后一个最大值不删
chunksMaxNum.splice(j, chunksMaxNum.length - j - 1);
break;
}
j += 1;
}
// 可单独为 chunk
if (!flag) {
chunksMaxNum.push(arr[i]);
}
i += 1;
}
return chunksMaxNum.length;
}
return 0;
};
解法 2
这是一种更简单的解法。
思路分析
由于元素的值在 [0, arr.length - 1] 范围内，所以排序后对应位置的元素为 i。如果到当前位置为止最大的数恰好为 i，那么它们可以成为一个区块。
比如：[1, 3, 0, 2, 4]，排序后的结果为：[0, 1, 2, 3, 4]。到当前位置为止，最大的数分别为：[1, 3, 3, 3, 4]。
对比这两组数字，可以发现刚好在有序位置上的数为 3 和 4。以它们为分隔点，可划分为 [1, 3, 0, 2] 和 [4] 两个区块。
最大值： [1, 3, 3, 3, 4]
排序后： [0, 1, 2, 3, 4]
所以，这种解法的核心是巧妙利用元素的范围。
代码实现
java 实现代码如下：
public class Solution {
public int maxChunksToSorted(int[] arr) {
if (arr != null && arr.length > 0) {
// 保存当前位置最大值
int[] maxNum = new int[arr.length];
int max = Integer.MIN_VALUE;
int result = 0;
for (int i = 0; i < arr.length; i++) {
// 计算最大值
max = Math.max(max, arr[i]);
maxNum[i] = max;
}
for (int i = 0; i < maxNum.length; i++) {
// 如果刚好等于排序后的数字，则可以单独成块
if (maxNum[i] == i) {
result += 1;
}
}
return result;
}
return 0;
}
}
