最大分块排序 (经典算法题500道),程序员经典面试笔试题目, 码小课

当前位置：面试刷题>> 最大分块排序 (经典算法题500道)

题目描述补充

题目：最大分块排序

给定一个整数数组 arr，我们需要将其重新排列成若干个非空子数组（或称为“块”），使得每个块内部是排序的（升序或降序都可以），并且要求所有块的最大值之和尽可能小。最后，返回这个最小的最大值之和。

示例：

输入：arr = [4, 3, 2, 1, 2, 3, 4]

输出：4

解释：我们可以将数组分成两个块 [4, 3, 2, 1] 和 [2, 3, 4]，每个块内部都是排序的（这里以升序为例），且两个块的最大值都是 4，所以最小的最大值之和为 4。

解题思路

这个问题可以通过二分查找结合贪心算法来解决。首先，我们需要确定一个“最大值”的阈值 x，然后尝试检查是否存在一种分块方式，使得所有块的最大值都不超过 x。

二分查找：设定二分查找的上下界，上界为数组中的最大值，下界为数组中的最小值（或者更小的数，但这里通常设为数组中的最小值即可）。
检查函数：对于给定的 x，检查是否可以将数组分成若干块，使得每块的最大值都不超过 x。这可以通过遍历数组，并使用贪心算法尽量填满每个块来实现。
贪心算法：从左到右遍历数组，如果当前元素小于等于 x，则将其加入当前块；如果当前元素大于 x，则结束当前块（如果当前块非空），并开启新的块。

示例代码

PHP 示例

function maxChunksToSorted(array $arr): int {
    $left = min($arr);
    $right = max($arr);
    
    while ($left < $right) {
        $mid = $left + floor(($right - $left) / 2);
        if (canDivideIntoSortedChunks($arr, $mid)) {
            $right = $mid;
        } else {
            $left = $mid + 1;
        }
    }
    
    return $left;
}

function canDivideIntoSortedChunks(array $arr, int $max): bool {
    $currentChunkMax = 0;
    $chunks = 0;
    
    foreach ($arr as $num) {
        if ($num > $max) {
            return false; // 如果有元素大于max，则无法分割
        }
        
        if ($num > $currentChunkMax) {
            $currentChunkMax = $num;
        }
        
        if ($currentChunkMax == $max) {
            $chunks++;
            $currentChunkMax = 0; // 开始新的块
        }
    }
    
    // 如果最后一个块不为空且其最大值小于等于max，则也计数
    if ($currentChunkMax <= $max) {
        $chunks++;
    }
    
    return $chunks > 0; // 至少需要一个块
}

// 示例用法
$arr = [4, 3, 2, 1, 2, 3, 4];
echo maxChunksToSorted($arr); // 输出 4

Python 示例

def maxChunksToSorted(arr):
    left, right = min(arr), max(arr)
    
    while left < right:
        mid = (left + right) // 2
        if can_divide_into_sorted_chunks(arr, mid):
            right = mid
        else:
            left = mid + 1
    
    return left

def can_divide_into_sorted_chunks(arr, max_val):
    current_max = 0
    chunks = 0
    
    for num in arr:
        if num > max_val:
            return False
        
        current_max = max(current_max, num)
        
        if current_max == max_val:
            chunks += 1
            current_max = 0
    
    # 检查最后一个块（如果它非空且最大值小于等于max_val）
    if current_max <= max_val:
        chunks += 1
    
    return chunks > 0

# 示例用法
arr = [4, 3, 2, 1, 2, 3, 4]
print(maxChunksToSorted(arr))  # 输出 4

JavaScript 示例

function maxChunksToSorted(arr) {
    let left = Math.min(...arr);
    let right = Math.max(...arr);
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (canDivideIntoSortedChunks(arr, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

function canDivideIntoSortedChunks(arr, max) {
    let currentMax = 0;
    let chunks = 0;
    
    for (let num of arr) {
        if (num > max) return false;
        
        currentMax = Math.max(currentMax, num);
        
        if (currentMax === max) {
            chunks++;
            currentMax = 0;
        }
    }
    
    // 如果最后一个块非空且其最大值小于等于max
    if (currentMax <= max) {
        chunks++;
    }
    
    return chunks > 0;
}

// 示例用法
const arr = [4, 3, 2, 1, 2, 3, 4];
console.log(maxChunksToSorted(arr)); // 输出 4