769. Max Chunks To Make Sorted

发表于

每日一题 2019 - 02 - 23

题目：

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:

1
2
3
4
5
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:

1
2
3
4
5
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开始的，那么我们可以这么思考，给定最大数字maxn

  • 如果当前的(maxn = max(arr[i],maxn) ) == i，那么证明这个位置i就可以是单独的一个块，因为不管怎么排序，这个位置依然是处于正确位置上的，那么就让结果 + 1
  • 如果当前最大的(maxn = max(arr[i],maxn) ) != i，那么证明这个位置i已经发生乱序，此时就不可以就需要继续往后遍历，把下一个位置的数据跟位置i的数据合成一组，继续判断是否满足单独成为一组的条件，如果不成立，那么继续往下一个位置走，并把下一个位置的数据加入到之前的两个数中；如果满足单独成为一组的条件，那么结果 + 1

代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int ans = 0;
        for (int i = 0, maxn = 0; i < arr.size(); i++) {
            maxn = max(arr[i], maxn);
            if (maxn == i) ans++;
        }
        return ans;
    }
};
0%
undefined