【LeetCode-769. medium】最多能完成排序的块

​​力扣​​

 解题报告：

注意这种【根据一个要求，将数组分成多个区间】类模型的问题（比如汽车加油站、加法表达式求和），套路就这三步：

1、初始化

2、for循环或者while，里面三步

        2.1 更新

        2.2 如果符合分割条件，则分割。

        2.3 初始化。（注意是初始化，最好不要直接用下一个的值，具体见代码标注）

3、处理末尾区间。

AC代码1：

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int st = 0, ans = 0, mn = 1000000,mx = -1;
        for(int i = 0; i<arr.size(); i++) {
            mn = min(mn, arr[i]);
            mx = max(mx, arr[i]);
            if(st == mn && i == mx) {
                st = i+1;    // AOE思想，<=i的已经都无了，直接i+1就是初始化
                mn = 1000000,mx = -1;    //规范写就初始化，而不是直接用arr[i+1]
                ans++;
            }
        }
        return ans;
    }
};

AC代码2：

考虑到数组长度为n，而且数组元素位于区间[0, n-1]且不重复，那么数组排好序后，每个值和下标恰好是相等的；所以，从左到右遍历数组，并且分别对值和下标累加求和，只要两个和相等，就切出一个块。（思路是a==c, a+b==c+d，则b=d，类似糖水不等式那种，初量和全量相等，则增量相等）

如此，时间复杂度O(n)，空间复杂度O(1)。

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int ret = 0;
        int vSum = 0;
        int iSum = 0;
        for(int i = 0; i < arr.length; i++){
            vSum += arr[i];
            iSum += i;
            if(vSum == iSum)ret++;
        }
        return ret;
    }
}