[数据结构与算法]力扣 769. 最多能完成排序的块

题目来源：https://leetcode.cn/problems/max-chunks-to-make-sorted/

大致题意：
给一个长度为 n 的数组，元素范围为 [1，n]，可以将数组分成连续的几个块，对每个块单独排序，块内有序后数组也整体有序。求最多能将数组分成几块。

比如数组 [2, 3, 1, 5, 4]，可以分成两块 [2, 3, 1] 和 [5, 4]，块内排序后整体也有序

思路

首先根据题意可知，数组直接分为一块进行块内排序，排序后数组整体一定有序

那么将数组分为两块呢？什么时候可以将数组分为两块？

假设现在数组可以分成两块 [0, i - 1] 和 [i, n - 1]，有 nums[x] 在块 [i, n - 1] 中，那么 nums[x] 的数值范围为 [i + 1, j + 1]。因为如果 nums[x] 小于等于 i，那么 nums[x] 应该在前 i 个数中，也就是应该在块 [0, i - 1] 中

也就是说，数组分块的标准就是块内的元素值刚好在分块索引覆盖范围内

同理，如果将数组分为多块，那么块 [i, j] 中的数都在 [i + 1, j + 1] 中

那么如何判断块的范围呢?

若现在已知上一个块的边界为 last - 1，在 [last, i] 中的最大值为 x，那么有：

1. 若 x > i + 1，那么在 i 之后一定有数小于 x，[last, i] 不能分块
2. 若 x == i + 1，已知在 [last, i] 中的值都不大于 x，那么 [last, i] 可以分块
3. 不存在 x < i + 1 的情况，因为前 last 个数都在之前的块中，剩余的 [i - last + 1] 个数字中的最大值一定大于等于 x

经过以上分析可以知道，如果目前遍历到的最大值等于当前遍历索引 + 1，那么当前位置到上一个分块边界可以进行分块

具体代码：

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int ans = 0;
        int preMax = -1;	// 目前遍历到的最大值
        int n = arr.length;
        for (int i = 0; i < n; i++) {
        	// 更新最大值
            preMax = Math.max(arr[i], preMax);
            // 分块条件
            if (preMax == i) {
                ans++;
            }
        }
        
        return ans;
    }
}