題目大意

給一個(gè)數(shù)組給你，數(shù)組里面全是數(shù)字，把數(shù)組分成獨(dú)立的塊，每塊獨(dú)立排序后和整個(gè)數(shù)組排序的結(jié)果相同， 問最多可以把這個(gè)數(shù)組分成幾塊

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].

解法一

思路

最開始想到的是，先整理好一份數(shù)組，然后對(duì)比

/**
 * @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會(huì)一直從數(shù)組頭開始查找，其實(shí)是可以優(yōu)化，用個(gè)變量存儲(chǔ)查找的地址

/**
 * @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
};

解法二

思路

這段代碼其實(shí)是我看別人做的，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)，很巧妙。數(shù)組的很多算法的解法，都是從兩邊同時(shí)開始，然后記錄一些信息。在本題中，記錄下從左邊開始的每一步的最大值列表，跟從右邊開始的每一步最小值列表。然后比較。如果某個(gè)數(shù)左邊的最大值小于其右邊的最小值，說明以這個(gè)數(shù)為界，可以切成獨(dú)立的小塊。

代碼示例

/**
 * @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;
};