最多能完成排序的块 II
难度:
标签:
题目描述
代码结果
运行时间: 26 ms, 内存: 16.4 MB
/*
* 思路:
* 使用Java Stream来简化代码,通过流操作来维护当前块的最大值和计数器。
* 同样,我们在遍历数组时,如果当前块的最大值等于当前位置的索引,
* 则说明可以分割出一个新的块。
*/
import java.util.stream.IntStream;
public class SolutionStream {
public int maxChunksToSorted(int[] arr) {
final int[] maxChunks = {0};
final int[] maxInCurrentChunk = {0};
IntStream.range(0, arr.length).forEach(i -> {
maxInCurrentChunk[0] = Math.max(maxInCurrentChunk[0], arr[i]);
if (maxInCurrentChunk[0] == i) {
maxChunks[0]++;
}
});
return maxChunks[0];
}
}
解释
方法:
此题解使用了一个单调递增栈的思路。遍历数组中的每个元素,对于当前元素n,如果栈为空或者n大于等于栈顶元素,则直接将n入栈。否则,说明当前元素n小于栈顶元素,需要进行合并操作:不断弹出栈顶元素,直到栈为空或者栈顶元素小于等于n,然后将之前弹出的最后一个元素重新压入栈中。最后,栈的长度就是最多能分成的块数。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法中,如何确定何时将弹出的元素重新压入栈中?这一步骤在保持块内顺序中起到了什么作用?
▷🦆
栈中存储的是什么具体的值?是原数组中的元素,还是某种经过处理的值?
▷🦆
该算法在处理具有多个相同值的数组时是如何操作的,例如在数组中遇到连续的相同元素应该怎么处理?
▷🦆
请解释在最后返回栈的长度作为能分成最多块数的依据,栈的长度代表了什么?
▷相关问题
最多能完成排序的块
给定一个长度为 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
中每个元素都 不同