标记所有元素后查找数组的分数

2593。标记所有元素后查找数组的分数

难度：中等

主题：堆（优先级队列）、排序、数组、模拟、哈希表、有序集、有序映射、贪心、单调堆栈、滑动窗口、两个指针、堆栈、队列、位操作、分而治之，动态规划，双向链表，数据流，基数排序，回溯，位掩码，树，设计，哈希函数、字符串、迭代器、计数排序、链表

给你一个由正整数组成的数组 nums。

从分数 = 0 开始，应用以下算法：

• 选择数组中未标记的最小整数。如果有平局，则选择索引最小的一个。
• 将所选整数的值添加到分数中。
• 标记所选元素及其两个相邻元素（如果存在）。
• 重复，直到所有数组元素都被标记。

返回应用上述算法后得到的分数。

示例1：

• 输入： nums = [2,1,3,4,5,2]
• 输出： 7
• 说明：我们对元素进行如下标记：
  • 1 是最小的未标记元素，因此我们标记它及其两个相邻元素：[2,1,3,4,5,2].
  • 2 是最小的未标记元素，因此我们标记它及其左相邻元素：[2,1,3,4,5,2].
  • 4 是唯一剩余的未标记元素，因此我们将其标记为：[2,1,3,4,5,2].
  • 我们的分数是 1 2 4 = 7。

示例2：

• 输入： nums = [2,3,5,1,3,2]
• 输出： 5
• 说明：我们对元素进行如下标记：
  • 1 是最小的未标记元素，因此我们标记它及其两个相邻元素：[2,3,5,1,3,2].
  • 2是最小的未标记元素，因为有两个，所以我们选择最左边的一个，所以我们标记索引为0的那个及其右邻元素：[2,3,5,1,3, 2].
  • 2 是唯一剩余的未标记元素，因此我们将其标记为：[2,3,5,1,3,2].
  • 我们的分数是 1 2 2 = 5。

约束：

• 1 5
• 1 6

提示：

1. 尝试模拟标记元素及其相邻元素的过程。
2. 如果有一个元素已经被标记，那么你就跳过它。

解决方案：

我们可以通过使用排序数组或优先级队列来跟踪最小的未标记元素来有效地模拟标记过程。所以我们可以使用以下方法：

计划：

1. 输入解析：读取数组nums并初始化分数和标记状态变量。
2. 堆（优先级队列）：
   • 使用最小堆高效提取每一步中最小的未标记元素。
   • 将每个元素及其索引（值、索引）插入堆中，以根据最小索引管理关系。
3. 标记元素：
   • 维护一个标记数组来跟踪某个元素及其相邻元素是否被标记。
   • 处理堆中的元素时，如果已标记则跳过它。
   • 标记当前元素及其两个相邻元素（如果存在）。
   • 将当前元素的值添加到分数中。
4. 重复：继续，直到所有元素都被标记。
5. 输出：返回累计分数。

让我们用 PHP 实现这个解决方案：2593。标记所有元素后查找数组的分数

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

// Example usage:
$nums1 = [2, 1, 3, 4, 5, 2];
$nums2 = [2, 3, 5, 1, 3, 2];

echo findScore($nums1) . "\n"; // Output: 7
echo findScore($nums2) . "\n"; // Output: 5
?>

解释：

1. 堆构建:

   • usort 函数根据值对数组进行排序，并在值绑定时按索引对数组进行排序。
   • 这确保我们始终处理具有最小索引的最小未标记元素。

2. 标记逻辑:

   • 对于每个未标记的元素，我们使用标记的数组来标记它及其相邻元素。
   • 这确保我们有效地跳过之前标记的元素。

3. 时间复杂度:

   • 对堆进行排序：O(n log n)
   • 处理堆：O(n)
   • 总体而言：O(n log n)，这对于给定的约束是有效的。

4. 空间复杂度:

   • 标记数组：O(n)
   • 堆：O(n)
   • 总计：O(n)

该解决方案满足约束条件，并且对于大输入有效地工作。

联系链接

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

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

• 领英
• GitHub

以上是标记所有元素后查找数组的分数的详细内容。更多信息请关注PHP中文网其他相关文章！