題目大意
給一個數組給你，數組里面全是數字匈棘，把數組分成獨立的塊，每塊獨立排序后和整個數組排序的結果相同逃默， 問最多可以把這個數組分成幾塊
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會一直從數組頭開始查找，其實是可以優(yōu)化乌妙，用個變量存儲查找的地址
/**
* @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;
};
