题目链接:https://leetcode.cn/problems/max-chunks-to-make-sorted-ii/

题目难度:困难

题意

这个问题和“最多能完成排序的块”相似,但给定数组中的元素可以重复,输入数组最大长度为2000,其中的元素最大为10**8。

arr是一个可能包含重复元素的整数数组,我们将这个数组分割成几个“块”,并将这些块分别进行排序。之后再连接起来,使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块?

示例 1:

输入: arr = [5,4,3,2,1]
输出: 1
解释:
将数组分成2块或者更多块,都无法得到所需的结果。
例如,分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3],这不是有序的数组。 

示例2:

输入: arr = [2,1,3,4,4]
输出: 4
解释:
我们可以把它分成两块,例如 [2, 1], [3, 4, 4]。
然而,分成 [2, 1], [3], [4], [4] 可以得到最多的块数。 

提示:

  • arr的长度在 [1, 2000]之间。
  • arr[i]的大小在 [0, 10**8]之间。

题解:排序+哈希

困难题唯唯诺诺,题目不难,难在问题转化。

首先定义一个数组sorted表示arr排序后的情况。首先将整个数组划分为一块肯定符合题意,于是思考划分为两块呢?设划分的位置为k,则:$arr[0]…arr[k]$和$sorted[0]…sorted[k]$中出现的所有元素及其频率一定是相同的,这样后面两部分($arr[k+1]…arr[n-1]$和$sorted[k+1]…arr[n-1]$)的所有元素及其频率也一定相同。

于是思考一般的情况:只要两个数组在一段距离(i-j)中出现的所有元素及其频率都一致则可以划分为一块。

具体实现思路为:用一个哈希表cnt,存储每个元素对应的数量,如果arr数组中出现则+1,如果sorted出现则减1,当然可以用两个哈希表分别表示arr数组和sorted数组的情况(只是空间更大而已)。具体见代码。

C++代码

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n=arr.size();
        map<int,int> cnt;
        vector<int> sorted=arr;
        sort(sorted.begin(),sorted.end());
        int ans=0;
        for(int i=0;i<n;i++){
            int x=arr[i],y=sorted[i];
          
            cnt[x]++;
            if(cnt[x]==0) cnt.erase(x);

            cnt[y]--;
            if(cnt[y]==0) cnt.erase(y);

            if(cnt.size()==0) ans++;
        }
        return ans;
    }
};

C++代码(两个哈希表)

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n=arr.size();
        map<int,int> cnt1;
        map<int,int> cnt2;
        vector<int> sorted=arr;
        sort(sorted.begin(),sorted.end());
        int ans=0;
        for(int i=0;i<n;i++){
            int x=arr[i],y=sorted[i];
            cnt1[x]++;
            cnt2[y]++;
            bool flag = true;
            for(auto it:cnt1){
                if(it.second == cnt2[it.first]) continue;
                flag = false;
                break;
            }
            if(flag) ans++;
        }
        return ans;
    }
};