Hard

题目描述

给你一个整数数组 arr。

我们将 arr 分割成若干 块（即分区），并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。

返回数组能分成的最多块数量。

示例 1：

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

示例 2：

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

提示：

  • 1 <= arr.length <= 2000
  • 0 <= arr[i] <= 10^8

提示： 对于每个位置 k，如果 arr[:k] 的某个排列等于 sorted(arr)[:k]，那么我们就应该在这里切分块。

解题思路

这道题的核心思想是找到所有可以分割的位置，使得左半部分排序后等于整个数组排序后的左半部分。

方法分析：

  1. 前缀和比较法（推荐）：对于位置 i，如果 arr[0:i+1] 排序后等于 sorted(arr)[0:i+1]，那么可以在位置 i 后面分割。我们可以通过比较前缀和来判断：如果原数组前 i+1 个元素的和等于排序数组前 i+1 个元素的和，且原数组前 i+1 个元素的最大值不超过排序数组第 i 个位置的值，那么就可以分割。

  2. 单调栈法：维护一个单调递增的栈，栈中存储每个块的最大值。遍历数组时，如果当前元素小于栈顶，说明需要合并块，将栈中大于当前元素的块都合并。

  3. 计数法：统计每个位置前缀的元素出现次数，与排序数组对应位置的前缀计数比较。

前缀和方法最直观且效率较高，通过预处理排序数组，然后逐个比较前缀和即可确定分割点。

代码实现

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        vector<int> sorted_arr = arr;
        sort(sorted_arr.begin(), sorted_arr.end());
        
        long long sum1 = 0, sum2 = 0;
        int chunks = 0;
        
        for (int i = 0; i < arr.size(); i++) {
            sum1 += arr[i];
            sum2 += sorted_arr[i];
            if (sum1 == sum2) {
                chunks++;
            }
        }
        
        return chunks;
    }
};

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

public class Solution {
    public int MaxChunksToSorted(int[] arr) {
        int[] sortedArr = new int[arr.Length];
        Array.Copy(arr, sortedArr, arr.Length);
        Array.Sort(sortedArr);
        
        long sum1 = 0, sum2 = 0;
        int chunks = 0;
        
        for (int i = 0; i < arr.Length; i++) {
            sum1 += arr[i];
            sum2 += sortedArr[i];
            if (sum1 == sum2) {
                chunks++;
            }
        }
        
        return chunks;
    }
}

var maxChunksToSorted = function(arr) {
    let n = arr.length;
    let leftMax = new Array(n);
    let rightMin = new Array(n);
    
    leftMax[0] = arr[0];
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], arr[i]);
    }
    
    rightMin[n - 1] = arr[n - 1];
    for (let i = n - 2; i >= 0; i--) {
        rightMin[i] = Math.min(rightMin[i + 1], arr[i]);
    }
    
    let chunks = 0;
    for (let i = 0; i < n - 1; i++) {
        if (leftMax[i] <= rightMin[i + 1]) {
            chunks++;
        }
    }
    
    return chunks + 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要消耗在排序操作上
空间复杂度O(n)需要额外的数组存储排序后的结果

相关题目