769. Max Chunks To Make Sorted ----M

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

A:

思路很简单：

每个开始的partition，（假设第一个）包含了从0----k-1的所有的数字，

因为是unique的，所以就可以根据最远距离（i.e.最大的数字区间。如果和找到的数的count相等，那么就是全找到了）

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        return helper(arr, 0);
    }
private:
    int helper(vector<int> & arr, int begin){// begin and end are inclusive
        int n = arr.size();
        if(begin>= n)
            return 0;
        int maxGap = 0;
        for(int i = begin;i<n;i++){
            maxGap = max(maxGap, arr[i] -begin );
            if(maxGap == i - begin){
                return 1 + helper(arr,i+1);
            }
        }
        return 1;
    }
};

官方的java答案：

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int ans = 0, max = 0;
        for (int i = 0; i < arr.length; ++i) {
            max = Math.max(max, arr[i]);
            if (max == i) ans++;
        }
        return ans;
    }
}