769. Max Chunks To Make Sorted解题

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.

假设在数组中存在一个变量A[i] != i, 那么为了最后让整个数组排好序，我们最起码要把从min(i, A[i]) 到 max(i, A[i])这个范围给排序，所以遍历一遍数组可能会有很多这种范围，用栈把这些范围中重合的那些组合起来就行了，最后答案就是栈里面剩下的没有重合的范围。

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();
    }
};