写点什么

LeetCode 769. Max Chunks To Make Sorted

用户头像
liu_liu
关注
发布于: 2020 年 06 月 07 日
LeetCode 769. Max Chunks To Make Sorted

问题描述


给定一个数组 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]


对比这两组数字,可以发现刚好在有序位置上的数为 34。以它们为分隔点,可划分为 [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; }}
复制代码


发布于: 2020 年 06 月 07 日阅读数: 51
用户头像

liu_liu

关注

不要相信自己的记忆力 2017.11.13 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode 769. Max Chunks To Make Sorted