769. 最多能完成排序的块

🟠   🔖  栈 贪心 数组 排序 单调栈  🔗 力扣 LeetCode

题目

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.

题目大意

给定一个长度为 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] 可以得到最多的块数。

对每个块单独排序后，结果为 [0, 1], [2], [3], [4]

提示:

• n == arr.length
• 1 <= n <= 10
• 0 <= arr[i] < n
• arr 中每个元素都 不同

解题思路

解题的关键是找到可以分块的位置：数组中前缀最大值等于对应的索引时，当前可以分割。

• 若从头遍历到位置 i 的子数组 [0, i] 的最大值等于 i，则可以将前缀 [0, i] 作为一个块。
  • 例如：对于数组 [1, 0, 2, 3, 4]：
    • [1, 0] 的最大值是 1，对应的索引也是 1，所以可以划分为一个块。
    • [2]、[3]、[4] 都满足上述条件。
• 如果最大值大于 i，说明当前块还不能结束。

1. 初始化变量：
   • maxVal：记录当前遍历的前缀的最大值。
   • chunks：记录分块的数量。
2. 遍历数组 arr：
   • 更新 maxVal 为当前遍历到的最大值。
   • 如果 maxVal 等于当前索引 i，说明可以分块，chunks 加一。
3. 遍历结束，返回分块数量。

复杂度分析

• 时间复杂度：O(n)，遍历数组一次。
• 空间复杂度：O(1)，仅使用了常数额外空间。

代码

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function (arr) {
	let maxVal = 0; // 当前前缀最大值
	let chunks = 0; // 分块数量

	for (let i = 0; i < arr.length; i++) {
		maxVal = Math.max(maxVal, arr[i]); // 更新前缀最大值
		if (maxVal === i) {
			// 最大值等于索引时，可以分块
			chunks++;
		}
	}

	return chunks;
};

相关题目

题号	标题	题解	标签	难度	力扣
768	最多能完成排序的块 II		栈 贪心 数组 2+	🔴	🀄️ 🔗