LeetCode 769. Max Chunks to Make Sorted I题目解析-wowAC

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

Note:

  • arr will have length in range [1, 10].

  • arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

题目复述

给定一个数组,内容是[0, 1, 2, … ,arr.length-1]的一个排列,将数组分成好几个片段,对于每一个片段内部进行排序,得到的结果数组等于对数组进行升序排序后的结果。问数组可以被分的最大片段数是多少?

例如:arr = [1, 0, 2, 3, 4],可以被分成[1, 0] [2, 3, 4]2个片段,内部排序后为[0, 1] [2, 3, 4]。于是可以被分为2个片段。

题目解析

显然排序后数字i应该放在目标位置i(即arr[i]),例如对于arr = [1, 0, 2, 3, 4],arr[0] = 1表示第0个位置的数1应该放置在目标位置1。有了这个结论在考虑答案的一个片段s-t,s-t内的所有数的目标位置都小于等于t。例如对于片段0-1,他两的目标位置分别为[1, 0],均小于等于1。有了这个结论,我们只需使用扫描法找出所有片段即可。

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int maxx = 0, ans = 0;
        for(int i=0; i<arr.size(); i++) {
            maxx = max(maxx, arr[i]);
            if(i == maxx) ans++;
        }
        return ans;
    }
};

发表评论

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