769. Max Chunks To Make Sorted

Leetcode link

题目简介

本题给了我们一个数组，要求我们对其分块后进行升序排列（分块就是将其拆分成任意长度的数组），要求分块后合并的排序结果要跟一开始的数组排序结果保持一致

解题思路

在题目的约束中，我们能够完成分块，有一个主要的原则：每个分块中，最小的数字必须在最后面，否则都能从该分块中拆出符合题目要求的别的分块来

基于这个原则我们来看一个例子：[0,1,4,3,2,5,6]

我们不难看出，这个例子最多能拆出 5 个分块：[0], [1], [4,3,2], [5], [6]

所以这题的难点在于要怎么把 [4,3,2] 这种情况判断出来

有意思的是，题目的限制给了我们线索，其中最关键的有两条：

- 0 <= arr[i] < n

- 数组中任何数字都是唯一的

这两条告诉我们，数组的下标与数字是一一对应的

那么，我们只需要遍历数组，一旦数组当前遍历下标的和与数组当前遍历值的和相等时，则表示可以分块

拓展一下，如果没有这两个条件我们该怎么做？

1. 将原数组深拷贝成一个新数组，并将其排序
2. 同时遍历新数组与原数组
3. 一旦他俩遍历过元素的和相等，则表示可以分块

Javascript

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function (arr) {
    let indexSum = 0
    let valueSum = 0
    let trunk = 0

    for (let i = 0; i < arr.length; i++) {
        indexSum += i
        valueSum += arr[i]
        if (indexSum === valueSum) {
            trunk++
        }
    }

    return trunk
};