。排序的最大块数

769。排序的最大块

难度：中等

主题：数组、堆栈、贪婪、排序、单调堆栈

给定一个长度为 n 的整数数组 arr，它表示 [0, n - 1] 范围内整数的排列。

我们将 arr 分成一定数量的块（即分区），并单独对每个块进行排序。连接它们后，结果应该等于排序后的数组。

返回我们可以对数组进行排序的最大块数。

示例1：

• 输入： arr = [4,3,2,1,0]
• 输出： 1
• 说明：
  • 分割成两个或更多块将不会返回所需的结果。
  • 例如，拆分为 [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] 是可能的最大块数。

约束：

• n == arr.length
• 1
• 0
• arr 的所有元素都是唯一。

提示：

1. 第一个块可以作为最小的 k 找到，其中 A[:k 1] == [0, 1, 2, ...k]；然后我们重复这个过程。

解决方案：

我们需要找到可以形成的最大块数，以便每个块都可以单独排序，并且当连接时，结果是整个数组的排序版本。

方法：

1. 关键观察：

   • 数组是从 0 到 n-1 的整数的排列。这个想法是遍历数组并找到可以分隔块的位置。
   • 如果对于块内的所有索引，直到该点的最大元素不超过原始排序数组中该点之后的最小元素，则可以对块进行排序。

2. 策略：

   • 跟踪从左向右遍历时遇到的最大值。
   • 在每个索引 i 处，检查 i 之前的最大值是否小于或等于 i。如果这个条件成立，则意味着您可以在该索引处拆分数组，因为左侧部分可以独立排序。

3. 步骤：

   • 迭代数组，同时保持运行最大值。
   • 每当运行最大值等于当前索引时，就可以创建一个块。
   • 计算这些块的数量。

让我们用 PHP 实现这个解决方案：769。排序的最大块数

<?php
/**
 * @param Integer[] $arr
 * @return Integer
 */
function maxChunksToSorted($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$arr1 = [4, 3, 2, 1, 0];
$arr2 = [1, 0, 2, 3, 4];

echo maxChunksToSorted($arr1); // Output: 1
echo "\n";
echo maxChunksToSorted($arr2); // Output: 4
?>

解释：

1. 初始化：

   • 我们从 maxSoFar = -1 开始，以确保我们在遍历数组时正确跟踪数组中的最大值。
   • chunks = 0 记录可以形成的块的数量。

2. 循环：

   • 我们循环遍历数组中的每个元素。
   • 对于每个元素，我们将 maxSoFar 更新为当前元素与之前看到的最大值之间的最大值。
   • 如果 maxSoFar == i，则意味着索引 i 之前的数组可以独立排序，这是一个有效的块。
   • 每次此条件成立时，我们都会增加块计数。

3. 返回：

   • 最后返回块的总数。

时间复杂度：

• 时间复杂度： O(n)，其中 n 是数组的长度。我们只遍历数组一次。
• 空间复杂度： O(1)，因为我们只使用几个变量来存储中间结果。

演练示例：

对于 arr = [1, 0, 2, 3, 4]：

• 在索引 0 处，到目前为止遇到的最大值是 1。我们不能在这里拆分。
• 在索引1处，最大值为1，与当前索引1匹配，因此我们可以分割成一个块。
• 在索引2处，最大值为2，它与索引2匹配，所以我们再次分裂。
• 在索引3处，最大值为3，它与索引3匹配，所以我们再次分裂。
• 在索引4处，最大值为4，它与索引4匹配，所以我们再次分裂。

因此，本例的输出是 4，因为我们可以将其分成 4 个块。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是。排序的最大块数的详细内容。更多信息请关注PHP中文网其他相关文章！