leetcode
leetcode 651 ~ 700
最多能完成排序的块 II

最多能完成排序的块 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小于栈顶元素时,会触发弹出操作,直到栈顶元素小于等于当前元素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 中每个元素都 不同