Medium

题目描述

给定一个长度为 n 的整数数组 arr，它表示在范围 [0, n-1] 内所有整数的一个排列。

我们将 arr 分割成若干个数据块（即分区），并对每个数据块单独排序。之后我们将所有排序的数据块连接起来，结果应该与排序后的数组相等。

返回我们能够分割的最大数据块数目。

示例 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] 可以得到最多的块数。

约束条件:

  • n == arr.length
  • 1 <= n <= 10
  • 0 <= arr[i] < n
  • arr 的所有元素都是唯一的。

解题思路

解题思路

这道题的核心思想是：当我们能够确定前 k 个位置的数字都能在前 k 个位置找到时，就可以形成一个独立的数据块。

由于数组是 [0, n-1] 的排列，排序后应该是 [0, 1, 2, …, n-1]。我们可以利用这个特性：

方法一：前缀最大值法（推荐）

  • 遍历数组，维护当前位置的前缀最大值
  • 如果在位置 i，前缀最大值等于 i，说明前 i+1 个元素恰好是 [0, 1, …, i] 的某个排列
  • 此时可以在位置 i 处切分，形成一个独立的数据块
  • 时间复杂度 O(n)，空间复杂度 O(1)

方法二：前缀和法

  • 计算前缀和，如果位置 i 的前缀和等于 0+1+…+i = i*(i+1)/2，说明可以切分
  • 原理相同，但需要额外的数学计算

方法三：单调栈法

  • 维护一个单调递增的栈，栈中存储每个数据块的最大值
  • 适用于更一般的情况，但对这道题稍显复杂

例如 [1,0,2,3,4]：

  • i=0: max=1, 1≠0，不能切分
  • i=1: max=1, 1=1，可以切分（第1个块：[1,0]）
  • i=2: max=2, 2=2，可以切分（第2个块：[2]）
  • i=3: max=3, 3=3，可以切分（第3个块：[3]）
  • i=4: max=4, 4=4，可以切分（第4个块：[4]）

总共4个数据块。

代码实现

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

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        chunks = 0
        max_so_far = 0
        
        for i in range(len(arr)):
            max_so_far = max(max_so_far, arr[i])
            if max_so_far == i:
                chunks += 1
        
        return chunks

public class Solution {
    public int MaxChunksToSorted(int[] arr) {
        int chunks = 0;
        int maxSoFar = 0;
        
        for (int i = 0; i < arr.Length; i++) {
            maxSoFar = Math.Max(maxSoFar, arr[i]);
            if (maxSoFar == i) {
                chunks++;
            }
        }
        
        return chunks;
    }
}

var maxChunksToSorted = function(arr) {
    let chunks = 0;
    let max = 0;
    
    for (let i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
        if (max === i) {
            chunks++;
        }
    }
    
    return chunks;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型前缀最大值法
时间复杂度O(n)
空间复杂度O(1)

相关题目