LeetCode 769. 最多能完成排序的块

Categories:

题目描述
思路分析
1. 解法一：前缀最大值（推荐）
相似题目

题目描述

✅ 769. 最多能完成排序的块

思路分析

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

核心思路：

题目保证数组为 0..n-1 的排列。

若当前位置 i 的前缀最大值 max 等于 i，说明该前缀可以独立排序成块。

统计所有满足条件的位置即可。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)。

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int max = 0;
        int chunks = 0;

        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            if (max == i) {
                chunks++;
            }
        }

        return chunks;
    }
}

func maxChunksToSorted(arr []int) int {
	maxVal := 0
	chunks := 0

	for i, v := range arr {
		if v > maxVal {
			maxVal = v
		}
		if maxVal == i {
			chunks++
		}
	}

	return chunks
}

相似题目

题目	难度	考察点
768. 最多能完成排序的块 II	困难	前缀/后缀
795. 区间子数组个数	中等	计数
763. 划分字母区间	中等	贪心
56. 合并区间	中等	贪心
452. 用最少数量的箭引爆气球	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/92338141