Description:

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:

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.

Link:

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

解題方法：

Let's say there is en element A[i] in our array. And A[i] != i (because this might be an unsorted array).
So in order to make this array sorted, we at least need to sort range from min(i, A[i]) to max(i, A[i]), if we scan this array, we will get a lot this kinda ranges, then, what we need to do is: try to combine those overlapped ranges.

A stack could achieve it. And the final result what we are looking for is the size of the stack.

假設(shè)在數(shù)組中存在一個變量A[i] != i, 那么為了最后讓整個數(shù)組排好序，我們最起碼要把從min(i, A[i]) 到 max(i, A[i])這個范圍給排序，所以遍歷一遍數(shù)組可能會有很多這種范圍，用棧把這些范圍中重合的那些組合起來就行了，最后答案就是棧里面剩下的沒有重合的范圍。

Time Complexity：

O(N)

完整代碼：

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<pair<int, int>> s;
        for(int i = 0; i < arr.size(); i++) {
            int start = min(i, arr[i]);
            int end = max(i, arr[i]);
            while(!s.empty() && s.top().second >= start) {
                start = min(start, s.top().first);
                end = max(end, s.top().second);
                s.pop();
            }
            s.push(pair<int, int> (start, end));
        }
        return s.size();
    }
};