LeetCode 769. Max Chunks To Make Sorted

liu_liu

关注

发布于: 2020 年 06 月 07 日

问题描述

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

复制代码

发布于: 2020 年 06 月 07 日阅读数: 51

原文链接:【http://xie.infoq.cn/article/78542a476645ca8dc8003d3c8】。文章转载请联系作者。

liu_liu

关注

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

还未添加个人简介

发布

暂无评论

创作场景

LeetCode 769. Max Chunks To Make Sorted

问题描述

解题思路

解法 1

思路分析

单区块

多区块

思路总结

代码实现

解法 2

思路分析

代码实现

liu_liu

评论