2593.md

title	description	keywords
2593. 标记所有元素后数组的分数	LeetCode 2593. 标记所有元素后数组的分数题解，Find Score of an Array After Marking All Elements，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 2593. 标记所有元素后数组的分数 标记所有元素后数组的分数 Find Score of an Array After Marking All Elements 解题思路 数组 哈希表 排序 模拟 堆（优先队列）

2593. 标记所有元素后数组的分数

🟠 Medium  🔖  数组 哈希表 排序 模拟 堆（优先队列）  🔗 力扣 LeetCode

题目

You are given an array nums consisting of positive integers.

Starting with score = 0, apply the following algorithm:

• Choose the smallest integer of the array that is not marked. If there is a tie, choose the one with the smallest index.
• Add the value of the chosen integer to score.
• Mark the chosen element and its two adjacent elements if they exist.
• Repeat until all the array elements are marked.

Return the score you get after applying the above algorithm.

Example 1:

Input: nums = [2,1,3,4,5,2]

Output: 7

Explanation: We mark the elements as follows:

• 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [_2_ ,_1_ ,_3_ ,4,5,2].
• 2 is the smallest unmarked element, so we mark it and its left adjacent element: [_2_ ,_1_ ,_3_ ,4,_5_ ,_2_].
• 4 is the only remaining unmarked element, so we mark it: [_2_ ,_1_ ,_3_ ,_4_ ,_5_ ,_2_].

Our score is 1 + 2 + 4 = 7.

Example 2:

Input: nums = [2,3,5,1,3,2]

Output: 5

Explanation: We mark the elements as follows:

• 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,3,_5_ ,_1_ ,_3_ ,2].
• 2 is the smallest unmarked element, since there are two of them, we choose the left-most one, so we mark the one at index 0 and its right adjacent element: [_2_ ,_3_ ,_5_ ,_1_ ,_3_ ,2].
• 2 is the only remaining unmarked element, so we mark it: [_2_ ,_3_ ,_5_ ,_1_ ,_3_ ,_2_].

Our score is 1 + 2 + 2 = 5.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

题目大意

给你一个数组 nums ，它包含若干正整数。

一开始分数 score = 0 ，请你按照下面算法求出最后分数：

• 从数组中选择最小且没有被标记的整数。如果有相等元素，选择下标最小的一个。
• 将选中的整数加到 score 中。
• 标记 被选中元素 ，如果有相邻元素，则同时标记 与它相邻的两个元素 。
• 重复此过程直到数组中所有元素都被标记。

请你返回执行上述算法后最后的分数。

示例 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 是最小未标记元素，由于有两个 2 ，我们选择最左边的一个 2 ，也就是下标为 0 处的 2 ，以及它右边相邻的元素：[_2_ ,_3_ ,_5_ ,_1_ ,_3_ ,2]。
• 2 是仅剩唯一未标记的元素，所以我们标记它：[_2_ ,_3_ ,_5_ ,_1_ ,_3_ ,_2_]。

总得分为 1 + 2 + 2 = 5 。

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

解题思路

1. 使用排序优化最小值查找

为了快速找到未标记的最小值，先将 nums 中的每个元素与其下标存入数组 arr，并按元素值升序排序。

这样，遍历 arr 时，最小值总是优先处理，避免每次查找时都遍历整个数组。

2. 使用集合记录标记状态

使用一个集合 marked 来记录已被标记的元素下标。

3. 遍历 arr

对每个元素，先判断其是否未被标记（!marked.has(idx)），若未标记则：

• 将该值累加到分数。
• 标记当前元素的下标以及其左右相邻的下标。

4. 返回最终分数

复杂度分析

• 时间复杂度：O(n log n)
  • 创建并排序数组 arr：O(n log n)
  • 遍历排序后的数组：O(n)
  • 总体复杂度：O(n log n)
• 空间复杂度：O(n)
  • 排序后的数组 arr 占用 O(n)
  • 用于记录标记状态的集合 marked 占用 O(n)
  • 总体空间复杂度：O(n)

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findScore = function (nums) {
	// 创建一个数组，包含每个元素及其原下标，并按值排序
	const arr = nums.map((num, idx) => [num, idx]).sort((a, b) => a[0] - b[0]);
	// 用于记录已标记的下标
	let marked = new Set();
	let score = 0;

	for (let [val, idx] of arr) {
		// 如果当前下标未被标记
		if (!marked.has(idx)) {
			// 累加分数
			score += val;
			// 标记当前元素
			marked.add(idx);
			// 标记相邻元素
			if (idx > 0) marked.add(idx - 1);
			if (idx < nums.length - 1) marked.add(idx + 1);
		}
	}

	return score;
};

相关题目

题号	标题	题解	标签	难度	力扣
1387	将整数按权重排序		记忆化搜索 动态规划 排序	🟠	🀄️ 🔗