原文链接: https://leetcode-cn.com/problems/max-chunks-to-make-sorted

英文原文

You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1].

We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.

Return the largest number of chunks we can make to sort the array.

 

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.

 

Constraints:

• n == arr.length
• 1 <= n <= 10
• 0 <= arr[i] < n
• All the elements of arr are unique.

中文题目

数组arr是[0, 1, ..., arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

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

示例 1:

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

示例 2:

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

注意:

• arr 的长度在 [1, 10] 之间。
• arr[i]是 [0, 1, ..., arr.length - 1]的一种排列。

通过代码

官方题解

方法一： 暴力

思路和算法

首先找到从左块开始最小块的大小。如果前 k 个元素为 [0, 1, ..., k-1]，可以直接把他们分为一个块。当我们需要检查 [0, 1, ..., n-1] 中前 k+1 个元素是不是 [0, 1, ..., k] 的时候，只需要检查其中最大的数是不是 k 就可以了。

[solution1-Pyton]
class Solution(object):
    def maxChunksToSorted(self, arr):
        ans = ma = 0
        for i, x in enumerate(arr):
            ma = max(ma, x)
            if ma == i: ans += 1
        return ans

[solution2-Java]
class Solution {
    public int maxChunksToSorted(int[] arr) {
        int ans = 0, max = 0;
        for (int i = 0; i < arr.length; ++i) {
            max = Math.max(max, arr[i]);
            if (max == i) ans++;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度: $O(N)$，其中 $N$ 为数组 arr 的长度。

• 空间复杂度: $O(1)$。

统计信息

通过次数	提交次数	AC比率
13631	23277	58.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
最多能完成排序的块 II	困难