LeetCode 2593 题解：标记所有元素后数组的分数（排序 + 访问标记模拟）-平芜编程栈

LeetCode 2593 题解：标记所有元素后数组的分数（排序 + 访问标记模拟）

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本文基于仓库 problems/2593.find-score-of-an-array-after-marking-all-elements.md 的官方题解展开，结合仓库收录情况与源码细节，完整讲解这道中等难度模拟题的题意、贪心思路、Python3 实现与复杂度分析。读完本文，你将掌握"排序后按值从小到大模拟标记"的套路，并能独立处理同类"带相邻连锁效应"的数组操作题。

题目地址与仓库收录

题目：2593. 标记所有元素后数组的分数（Find Score of an Array After Marking All Elements）
原题地址：https://leetcode.cn/problems/find-score-of-an-array-after-marking-all-elements/
仓库收录：本题解位于 problems/2593.find-score-of-an-array-after-marking-all-elements.md，并在仓库 README.md 与 SUMMARY.md 的题解目录中均有收录（README 第 445 行、SUMMARY 第 281 行），属于仓库"经典题目解析"部分的中等难度题目之一。

题目描述

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

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

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

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

示例 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

前置知识

哈希表（用于记录每个元素的访问 / 标记状态）

思路分析：排序 + 贪心模拟

为什么可以按排序后的顺序处理？

题目要求"每次选择最小且未标记的整数"。无论标记如何扩散，被选中的元素都必然是当前未标记集合中的最小值。因此可以先把nums排序，从小到大依次取出候选值；每次取出后，如果它尚未被标记，就累加分数并标记它本身及其左右邻居；如果已被标记，则直接跳过。

这一贪心策略之所以正确，是因为：

排序保证了"当前最小"这一约束始终满足；
标记状态只在取元素时被写入，排序结果不受影响；
每轮选中的元素一旦被标记就不会再被选中，流程与题目描述完全一致。

模拟过程推演（以示例 1 为例）

nums = [2,1,3,4,5,2]，按值排序后为1, 2, 2, 3, 4, 5，依次处理：

取最小未标记值1（原下标 1）：标记下标 1、0、2，分数score = 1；
值2：下标 0 已被标记跳过，下标 5 未被标记，选中并标记下标 5、4（下标 6 越界忽略），score = 1 + 2 = 3；
值3（下标 2）已被标记跳过；
值4（下标 3）未标记，标记下标 3、2、4（均已标记），score = 3 + 4 = 7；
值5（下标 4）已被标记跳过。

最终得分为7，与题目输出一致。可以注意到：尽管存在两个值为2的元素，算法在"值相等时选择下标最小"的规则下依然只按访问状态判断，天然满足该约束。

下标偏移的妙用

原题解代码使用了enumerate(nums, 1)，让下标从 1 开始计数，并配合vis = [False] * (len(nums) + 2)构造一个左右各多留一个空位的访问标记数组。这样在标记i-1和i+1时：

当i = 1（原下标 0，数组首元素）时，i-1 = 0落在额外开辟的哨兵位上，不会越界；
当i = n（原下标 n-1，数组尾元素）时，i+1 = n+1同样落在哨兵位上。

从而避免了在每个分支里写越界判断，代码更简洁且安全。

关键点

用哈希表 / 布尔数组记录每个元素的访问（标记）状态；
排序后从小到大取未标记元素，命中后更新左右邻居的访问状态；
访问标记数组左右各扩充一位（哨兵），简化边界处理；
取元素前必须先判断是否已访问，已访问则跳过。

代码实现（Python3）

class Solution: def findScore(self, nums: List[int]) -> int: ans = 0 vis = [False] * (len(nums) + 2) # 保证下标不越界 for i, x in sorted(enumerate(nums, 1), key=lambda p: p[1]): if not vis[i]: vis[i - 1] = True vis[i + 1] = True # 标记相邻的两个元素 ans += x return ans

代码要点逐行拆解：

enumerate(nums, 1)：为每个元素生成(下标, 值)对，下标从 1 开始，为哨兵位设计服务；
sorted(..., key=lambda p: p[1])：按值升序排列，保证每次取到的是"当前最小"；
vis[i - 1] = True、vis[i + 1] = True：标记选中元素的两个邻居（选中元素本身因后续循环中被排序固定、且不会再被选中，无需单独置位也能保证正确性——当然若值相等，已选中的下标在后续遇到时也会因vis[i]已被邻居标记而跳过）；
if not vis[i]：核心判断，保证不重复累加已被标记的索引；
ans += x：将选中值累加入总分。

关于最后一点值得展开：被选中的元素自身并不需要在选中当轮显式标记，因为排序后每个(下标, 值)对只会被遍历一次；当后续轮次再次遇到该下标时，它早已被某次操作标记（可能是作为被选中的元素被自己或邻居的标记覆盖），vis[i]为True自然被跳过。从代码逻辑可以推断，即使两个相同值相邻，先被选中的那个也会把另一个标记掉，这与"值相等选择下标最小"的规则完全吻合。

复杂度分析

令n为数组长度：

时间复杂度：O(n log n)。主要开销在于对n个(下标, 值)对进行排序；排序后的遍历为线性扫描，每次循环内是 O(1) 的数组访问与赋值。
空间复杂度：O(n)（以本实现而言）。vis数组长度为n + 2，占 O(n) 空间；排序本身是否产生额外空间取决于内置排序算法的实现（Python 的 TimSort 为 O(n) 辅助空间）。原题解将其表述为"不确定，取决于内置的排序算法"，是指排序辅助空间；若只统计显式数据结构，则vis数组严格为 O(n)。

同类题目延伸：排序 + 访问标记思想在仓库中的应用

"排序后按约束顺序处理 + 状态标记跳过"是高频套路，仓库中还有多道题目与之思想相通，可以对照学习：

2007. 从双倍数组中还原原数组：同样需要对数组排序，从小到大确定元素归属，并用"已使用"状态避免重复选取；
2592. 最大化数组的伟大值：与本题同属 2590 系列周赛题，同样依赖排序后贪心匹配；
上述题目均收录于仓库 problems 目录，可在 README.md 的题目索引中按编号快速定位。

这类题目的共性解题模板可以总结为三步：排序确定处理顺序 → 状态数组记录占用/标记 → 顺序遍历时跳过已被处理的位置。掌握这一模板，遇到"每次选最小/最大 + 禁止重复 + 连锁影响邻居"的模拟题都能快速切入。

小结

LeetCode 2593 是一道披着模拟外衣的贪心排序题。核心在于：

用排序保证"每次取最小未标记元素"；
用布尔数组记录访问状态，处理"相邻连锁标记"；
通过下标偏移 + 哨兵位，让边界处理变得优雅无分支。

整体解法 O(n log n) 时间、O(n) 空间，在n <= 10^5的约束下可以轻松通过。推荐配合仓库 problems/2593.find-score-of-an-array-after-marking-all-elements.md 原文反复揣摩，并结合上述同类题目加深对该套路的理解。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考