769. Max Chunks To Make Sorted

Description

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

Solution

Max jump, O(n), S(1)

Let's try to find the smallest left-most chunk. If the first k elements are [0, 1, ..., k-1], then it can be broken into a chunk, and we have a smaller instance of the same problem.

We can check whether k+1 elements chosen from [0, 1, ..., n-1] are [0, 1, ..., k] by checking whether the maximum of that choice is k.
因为题目要求chunk越多越好，最多的情况就是所有元素都在自己位置上，这样就是n个chunks。最少的情况比如倒序，这样只能是1个chunk。

解决起来也很简单，找到最短的连续元素使其排序后的位置跟现在相同即可。这里用jump记录当前遇到的最大元素，也就是最远的目标index。总感觉跟max jump题什么的很像。

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