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

最多能完成排序的块

难度:

标签:

题目描述

代码结果

运行时间: 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 == i`时,说明从数组的起始到当前位置i的最大值刚好是i。由于数组元素是从0开始连续的整数,不考虑重复元素的情况下,如果最大值是i,那么从0到i必须包含了所有小于等于i的整数,这样才能保证这部分是完整的并且可以独立于数组的其他部分进行排序。因此,每当检测到`cur_max == i`时,可以确信这一部分数组可以形成一个独立的块。
🦆
如果数组中存在重复元素,此算法是否仍然适用?
如果数组中存在重复元素,那么原算法将不再适用。这是因为重复元素会打破从0到i的索引与值一一对应的关系,导致即使`cur_max == i`也不能保证这之前的所有整数都已经出现。例如,数组[0, 1, 1, 2]中,尽管在索引2时`cur_max == 2`,但0到2的块并不能独立排序,因为它缺少数字0或1的另一个副本。因此,算法需要调整以适应包含重复元素的情况。
🦆
为什么更新当前最大值`cur_max`是用来确定是否可以形成一个块的条件?
在这个算法中,更新当前最大值`cur_max`并用它来确定是否可以形成一个块,是因为这个最大值可以帮助我们了解从数组开始到当前位置的元素范围。如果当前的最大值恰好等于当前的索引,那么意味着从0到该索引的所有整数都至少已经出现过一次,从而可以形成一个可以独立排序的块。这种方法依赖于数组元素与其索引位置之间的这种特定关系,是判断能否形成块的一个简单而有效的条件。
🦆
在极端情况下,例如数组已经是排序状态或完全逆序,这种算法的表现如何?
在数组已经是排序状态(例如[0, 1, 2, 3])的情况下,该算法表现良好,因为每个元素的索引与其值相等,`cur_max`将会在每个位置都等于索引,从而每个元素都可以形成一个块,块的数量等于数组的长度。相反,在完全逆序的情况下(例如[3, 2, 1, 0]),`cur_max`始终为数组的最大元素,直到遍历到最后一个元素时`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