Leetcode - 769 Max Chunks To Make Sorted (Medium)
题目描述：数组 arr 是 [0, 1, …, arr.length - 1] 的全排列，将数组分割成块，块内的元素可进行排序，块与块的相对位置不变，要想将整个数组升序排列，求做多能分成多少块。
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.解题思路：先来看看排序后的数组，以 [1,0,2,3,4] 为例，排序后为 [0,1,2,3,4]，也就是 arr[i] = i，下标与元素相等，那么在原数组中，只要与下标不相等的元素，一定需要进行排序，放到对应的下标位置，例如，排序后数组中的 1 会移动到 index = 1 的位置，那么 index = 0 和 index = 1 的两个位置一定在同一个块内，这样才能使元素 1 和 0 排序。所以，此题的解法可以向后遍历记录最大值，如果最大值移动到了对应下标位置，块数就可加一。例如 [4,3,2,1,0] 从头开始最大值一直是 4，直到遍历完毕才能把 4 移动到正确位置，所以只能分成 1 块。
public int maxChunksToSorted(int[] arr) { int max = 0, count = 0; for (int i = 0; i < arr.length; i++) { max = Math.max(max, arr[i]); if (max == i) count++; } return count; }