问题：
给一个数组（这一题可以有重复的数字），我们将其最多分成几块，各自进行全排序，能得到整体有序的数列？
数值大小范围增大，元素个数增多
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].
解法：
构建两个数组：
* 左边最大值数组 leftmax
* 右边最小值数组 rightmin
左边最大【i】<=右边最小【i+1】(因为存在可重复数字)【满足有序的情况】
那么res++
代码参考：
1 class Solution { 2 public: 3 int maxChunksToSorted(vector<int>& arr) { 4 int n=arr.size(), res=1; 5 vector<int> rightmin = arr, leftmax = arr; 6 for(int i=1; i<n; i++){ 7 leftmax[i]=max(leftmax[i],leftmax[i-1]); 8 } 9 for(int i=n-2; i>=0; i--){ 10 rightmin[i]=min(rightmin[i],rightmin[i+1]); 11 } 12 for(int i=0; i<n-1; i++){ 13 if(rightmin[i+1]>=leftmax[i]) res++; 14 } 15 16 return res; 17 } 18 };
可简化构建leftmax的过程，合并至最后一步的判断大小中，且简化数组为单个当前最大值 curmax
代码参考：
1 class Solution { 2 public: 3 int maxChunksToSorted(vector<int>& arr) { 4 int n=arr.size(), res=1; 5 vector<int> rightmin = arr; 6 int curmax=arr[0]; 7 for(int i=n-2; i>=0; i--){ 8 rightmin[i]=min(rightmin[i],rightmin[i+1]); 9 } 10 for(int i=0; i<n-1; i++){ 11 curmax=max(curmax, arr[i]); 12 if(rightmin[i+1]>=curmax) res++; 13 } 14 15 return res; 16 } 17 };
768. Max Chunks To Make Sorted II
原文：https://www.cnblogs.com/habibah-chang/p/12836569.html