768. Max Chunks To Make Sorted II

https://leetcode.com/problems/max-chunks-to-make-sorted-ii/

对给定数组分partition，要求每个partition的数字刚好是对数组排序后落在这些位置的数字，问最多能分几个partitions。max+partition最直接的想法就是DP，但这道题有更快和简便的做法，两种解法分别利用了这道题的两个性质。1. expected = sorted(nums), 那么nums[i,j]能被分到一个partition <=> sum(expected[i, j]) == sum(nums[i, j])。用反证法可以证明，这里就不赘述了。

/*
 * @lc app=leetcode id=768 lang=cpp
 *
 * [768] Max Chunks To Make Sorted II
 */

// @lc code=start
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        const int N = arr.size();
        vector<int> expected(arr);
        sort(expected.begin(), expected.end());
        int res = 0;
        long sum = 0, sum2 = 0;
        for (int i = 0; i < N; ++i) {
            sum += arr[i];
            sum2 += expected[i];
            if (sum == sum2) ++res;
        } 
        return res;
    }
};
// @lc code=end

2. nums[i, j]能分成一个partition <=> j之后不会有元素比nums[i , j]中最大的数小。因此对每个i先统计从前面遍历过来当前最大值，且统计从后面遍历过来的当前最小值，然后对每个i看从前面过来的最大是否小于后面过来的最小。

/*
 * @lc app=leetcode id=768 lang=cpp
 *
 * [768] Max Chunks To Make Sorted II
 */

// @lc code=start
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        const int N = arr.size();
        vector<int> f(arr), b(arr);
        for (int i = 1; i < N; ++i) f[i] = max(f[i - 1], arr[i]);
        for (int i = N - 2; i >= 0; --i) b[i] = min(b[i + 1], arr[i]);
        int res = 1;
        for (int i = 0; i < N - 1; ++i) {
            if (f[i] <= b[i + 1]) ++res;
        } 
        return res;
    }
};
// @lc code=end

解法参考自这。