768. Max Chunks To Make Sorted II

题目

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?

思路

一开始想的是找出单调非减序列，num不变，否则num++就可以了。后来发现[4,2,2,1,1]和[0,0,1,1,1]对相等的数的处理是截然相反的。我试图通过一个last标记上次是增还是减来决定下次是加还是不加，但是对于后者还是不起作用。看来我想的太简单了。

说实话答案没看懂，但是看到讨论区里一个O(n)的算法很好，基本上上面的思想相同，但是他借助的是左边序列的最小值和右边序列的最大值进行比较，如果minLeft<=maxRight则num++.

代码

一开始的代码：

int maxChunksToSorted(vector<int>& arr) {

if(arr.size()==0) return 0;
int num=0;int last=1;
for(int i=0;i<arr.size()-1;i++)
{
    if(arr[i+1]>arr[i]) {num++;last=1;}
    if(arr[i+1]==arr[i] && last==1) {num++;}
    
}
num++;
return num;

}

正确代码：

int maxChunksToSorted(vector<int>& arr) {

    if(arr.size()==0) return 0;

    vector<int> maxOfLeft(arr),minOfRight(arr);

    for(int i=1;i<arr.size();i++)
    {
        if(arr[i]>maxOfLeft[i-1]) maxOfLeft[i]=arr[i];
        else maxOfLeft[i]=maxOfLeft[i-1];

    }

    for(int i=arr.size()-2;i>=0;i--)
    {
        if(arr[i]<minOfRight[i+1]) minOfRight[i]=arr[i];
        else minOfRight[i]=minOfRight[i+1];
    }

    int num=0;
    for(int i=0;i<arr.size()-1;i++)
    {
        if(maxOfLeft[i]<=minOfRight[i+1]) num++;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
    }
    return num+1;
}