题目大意

给一个数组给你，数组里面全是数字，把数组分成独立的块，每块独立排序后和整个数组排序的结果相同， 问最多可以把这个数组分成几块

Problem

Given an array arr of integers (not necessarily distinct), we split the array into some number of "chunks" (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Input: arr = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.

Example 2:

Input: arr = [2,1,3,4,4]
Output: 4
Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.

Note:

• arr will have length in range [1, 2000].
• arr[i] will be an integer in range [0, 10**8].

解法一

思路

最开始想到的是，先整理好一份数组，然后对比

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function(arr) {
    let sortArr = arr.slice().sort((a,b) => a - b);
    
    let splits = 0;
    
    let max = 0;
    for(let i = 0; i< arr.length; i++){
        if(arr[i] === sortArr[i] && max === i){
                max = i + 1;
                splits += 1;
        } else {
            let pos = sortArr.indexOf(arr[i]);
            sortArr[pos] = -1;
            max = Math.max(pos,max);
            if(max === i) splits += 1;
        }   
    }

    return splits
};

由于indexOf会一直从数组头开始查找，其实是可以优化，用个变量存储查找的地址

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function(arr) {
    let sortArr = arr.slice().sort((a,b) => a - b);
    
    let splits = 0;
    
    let max = 0;
    let start = 0;
    for(let i = 0; i< arr.length; i++){
        if(arr[i] === sortArr[i] && max === i){
                max = i + 1;
                start = max;
                splits += 1;
        } else {
            let pos = sortArr.indexOf(arr[i],start);
            sortArr[pos] = -1;
            max = Math.max(pos,max);
            if(max === i) {
                splits += 1;
                start = max;
            }
        }
        
    }
    
    return splits
};

解法二

思路

这段代码其实是我看别人做的，时间复杂度为O(n)，空间复杂度为O(n)，很巧妙。数组的很多算法的解法，都是从两边同时开始，然后记录一些信息。在本题中，记录下从左边开始的每一步的最大值列表，跟从右边开始的每一步最小值列表。然后比较。如果某个数左边的最大值小于其右边的最小值，说明以这个数为界，可以切成独立的小块。

代码示例

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function(arr) {
    let leftMax = new Array(arr.length);
    let rightMin = new Array(arr.length);
    leftMax[0] = arr[0];
    
    for(let i = 1; i<arr.length; i++){
        leftMax[i] = Math.max(leftMax[i-1], arr[i]);
    }
    rightMin[arr.length -1] = arr[arr.length - 1]
    for(let i = arr.length - 2; i>= 0; i--){
        rightMin[i] = Math.min(rightMin[i+1], arr[i]);
    }
    
    let total = 1;
    for(let i = 0; i< arr.length-1; i++){
        if(leftMax[i] <= rightMin[i+1]) total++;
    }
    return total;
};