最多能完成排序的块
难度:
标签:
题目描述
代码结果
运行时间: 22 ms, 内存: 16.0 MB
/*
* 题目思路:
* 使用Java Stream计算最大块数。
* 使用IntStream遍历数组元素,并维护最大值。
* 当最大值等于当前索引时,增加块数。
*/
import java.util.stream.IntStream;
public class MaxChunksToSortedStream {
public int maxChunksToSorted(int[] arr) {
final int[] max = {0};
return (int) IntStream.range(0, arr.length)
.filter(i -> {
max[0] = Math.max(max[0], arr[i]);
return max[0] == i;
})
.count();
}
}
解释
方法:
题解的思路是迭代数组并维护当前遍历到的元素的最大值 cur_max。对于每个位置 i,如果 cur_max 等于 i,这意味着从 0 到 i 的元素正好是 0 到 i 的所有整数,因此可以形成一个块。每当这种情况发生时,块的计数器 chunks 就增加 1。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
如何确保在每次迭代时,`cur_max == i` 确实意味着可以形成一个块?
▷🦆
如果数组中存在重复元素,此算法是否仍然适用?
▷🦆
为什么更新当前最大值`cur_max`是用来确定是否可以形成一个块的条件?
▷🦆
在极端情况下,例如数组已经是排序状态或完全逆序,这种算法的表现如何?
▷相关问题
最多能完成排序的块 II
给你一个整数数组 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] <= 108