文章目录
  1. 1. 题意描述
  2. 2. 题意翻译
  3. 3. 结题思路
  4. 4. 代码参考:

题意描述

Given an array arr that is a permutation of [0, 1, …, arr.length - 1], 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 = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn’t sorted.

Example 2:
Input: arr = [1,0,2,3,4]
Output: 4

Explanation:

We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

Note:

arr will have length in range [1, 10].
arr[i] will be a permutation of [0, 1, …, arr.length - 1].

题意翻译

这里大概是说给一个大小为 N 的全排列后的数组,然后将这个数组分块,并对每一个块内的元素进行排序,并能保证每个块内的元素排序后拼接起来会得到原排序数组,求最大能分块的数量。

结题思路

思路这里一开始我也没有什么好办法,后来受到启发可以用类似greed的方法来解决。我们在每个位置上保存该位置上的数和之前的数相比得到的最大值,然后将这个最大值和数组的下标来比较。有多少个相同的就可以分为多少个。
这里有一个例子:

original: 0, 2, 1, 4, 3, 5, 7, 6

max:       0, 2, 2, 4, 4, 5, 7, 7

sorted:   0, 1, 2, 3, 4, 5, 6, 7

index:     0, 1, 2, 3, 4, 5, 6, 7

代码参考:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int maxChunksToSorted(int[] arr) {
// 基本思路 greedy , 先找出每个位置上的最大, 然后与排序后的数组比较
int max = 0;
int count = 0;
// travel the arr
for(int i=0 ; i<arr.length ; i++){
max = Math.max(arr[i] , max);
if(max == i){
count++;
}
}
return count;
}
}
文章目录
  1. 1. 题意描述
  2. 2. 题意翻译
  3. 3. 结题思路
  4. 4. 代码参考: