769. Max Chunks To Make Sorted

Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], 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 = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

Example 2:

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.

Note:

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

• arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

想紀錄一個largest array代表每個position的時候當前看過的數字最大值是多少。 拿題目給的example來看。 Original array: [1, 0, 2, 3, 4] Largest array: [1, 1, 2, 3, 4] | | | | | 只要遇到一個position他的largest是index本身，那就可增加一段，所以可以切成四段。

// Two Pass with O(n) Space Usage
int maxChunksToSorted(vector<int>& arr) { // time: O(n); space: O(n)
    if (arr.empty()) return 0;
    int n = arr.size(), res = 0;
    vector<int> largest(n, 0);
    largest[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        largest[i] = max(largest[i - 1], arr[i]);
    }
    for (int i = 0; i < n; ++i) {
        if (largest[i] == i) ++res;
    }
    return res;
}

但其實largest不需要用到1-D array來保存，因為每次只會需要前一個的最大值，所以只要用一個變數就可以。

// One Pass with O(1) Space Usage
int maxChunksToSorted(vector<int>& arr) { // time: O(n); space: O(1)
    if (arr.empty()) return 0;
    int n = arr.size(), res = 0, largest = 0;
    for (int i = 0; i < n; ++i) {
        largest = max(largest, arr[i]);
        if (largest == i) ++res;
    }
    return res;
}