LeetCode 768. Max Chunks To Make Sorted II题目解析-wowAC

Description

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?

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].


题目复述

给定一个整型数组(可能存在重复),将此数组分离成一些连续的块区间,对于每个块区间内部进行升序排序,之后合并这些块得到的结果和升序排序这个整型数组的结果相同,问最多分成几个块区间。例如arr = [2, 1, 3, 4, 4],可以分成[2, 1] [3, 4, 4],块内排序得到[1, 2] [3, 4, 4],合并后的结果[1, 2, 3, 4, 4]。满足题目条件,但是分成[2, 1] [3] [4] [4]也满足条件,因此可以分为的最大块区间为4。

题目解析

这道题是LeetCode 769的加强版,建议先做LeetCode 769,因为题中arr[i]可能会高达10**8,因此我们首先对arr数组进行离散化处理,最小的数映射为0,次小为1,依次类推,考虑arr中的数互不相同的情况,此时经过离散化的数组完全转化为LeetCode 769,考虑有重复数字的情况,对于某个arr数组中的某个数字而言,排序后的位置即小于它的数的数量,例如[1, 0, 2, 3, 3],1应该放在位置1,因为小于1的数只有1个,对于3而言,小于3的数的个数为3,因此他应该放在位置3,这里的问题是3有两个,因此我们就需要在放置了一个3之后调整一下后面的3应该放置的位置,即在3放置之后将3应该放置的位置+1,代码里面有cnt数组,cnt[i]表示数字i应该放置的位置,初始情况下cnt[i]等于小于i的数的数量,在放置一个数之后应该对cnt[i]+=1。

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        //离散化为0 - ed-arr_temp.begin()-1
        vector<int> arr_temp(arr);
        sort(arr_temp.begin(), arr_temp.end());
        vector<int>::iterator ed = unique(arr_temp.begin(), arr_temp.end());
        for(int i=0; i<arr.size(); i++) {
            arr[i] = lower_bound(arr_temp.begin(), ed, arr[i])-arr_temp.begin();
        }
        
        vector<int> cnt(ed-arr_temp.begin());
        //统计小于i的个数
        for(int i=0; i<arr.size(); i++)
            cnt[arr[i]]++;
        int temp = 0;
        for(int i=0; i<cnt.size(); i++) {
            int tp = cnt[i];
            cnt[i] = temp;
            temp += tp;
        }
        //求解答案
        int res = 0, maxx = 0;
        for(int i=0; i<arr.size(); i++) {
            maxx = max(maxx, cnt[arr[i]]);
            cnt[arr[i]]++;
            if(maxx == i)
                res++;
        }
        return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注