768. Max Chunks To Make Sorted II

This question is the same as "Max Chunks to Make Sorted" except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements could be up to 10**8.

Given an array arr of integers (not necessarily distinct), 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 = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.

Example 2:

Input: arr = [2,1,3,4,4]
Output: 4
Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.

Note:

• arr will have length in range [1, 2000].

• arr[i] will be an integer in range [0, 10**8].

可以用一個tmp array儲存sorted arr。用兩個變數分別紀錄traverse到某個index當下的和，如果和一樣，就代表可以形成一個chunk。 E.g. arr = [2, 1, 3, 4, 4] sort之後tmp = [1, 2, 3, 4, 4] i = 0, sum1 = 2, sum2 = 1 i = 1, sum1 = 3, sum2 = 3 (V) i = 2, sum1 = 6, sum2 = 6 (V) i = 3, sum1 = 10, sum2 = 10 (V) i = 4, sum1 = 14, sum2 = 14 (V)

// O(nlogn) Solution
int maxChunksToSorted(vector<int>& arr) { // time: O(nlogn); space: O(n)
    long sum1 = 0, sum2 = 0;
    int res = 0;
    vector<int> tmp = arr;
    sort(tmp.begin(), tmp.end());
    for (int i = 0; i < arr.size(); ++i) {
        sum1 += arr[i];
        sum2 += tmp[i];
        if (sum1 == sum2) ++res;
    }
    return res;
}

一開始想紀錄在traverse到某一個index的時候，左側的最大值如果小於等於右側的最小值，那就可以形成一個chunk。不需要用到2個1-D array去紀錄左側最大值和右邊最小值，在這邊選擇用1個1-D array minR去紀錄右側最小值，左側最大值可以用一個變數maxR隨著for loop去變換。

// O(n) Solution
int maxChunksToSorted(vector<int>& arr) { // time: O(n); space: O(n)
    int n = arr.size();
    vector<int> minR(n, 0);
    minR[n - 1] = arr[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        minR[i] = min(minR[i + 1], arr[i]);
    }
    int res = 1, maxL = -1;
    for (int i = 0; i < n - 1; ++i) {
        maxL = max(maxL, arr[i]);
        if (maxL <= minR[i + 1]) ++res;
    }
    return res;
}

769. Max Chunks To Make Sorted