# 2593. 标记所有元素后数组的分数
### 题目地址(2593. 标记所有元素后数组的分数)
### 题目描述
```
给你一个数组 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 <= 105
1 <= nums[i] <= 106
```
### 前置知识
* 哈希表
### 公司
* 暂无
### 思路
将 nums 排序，并从小到大取，比如当前取的是索引为 i 的。那么取完要更新：
1. 索引 i 为已访问
2. 索引 i-1 为已访问（如果存在）
3. 索引 i+1 为已访问（如果存在）
更新完访问状态后更新一下得分，即将分数加上 nums\[i] 即可。
当然，我们在取 i 之前要先判断是否已访问，如果未访问才执行上面的操作。
### 关键点
* 哈希表记录每个元素的访问状态
### 代码
* 语言支持：Python3
Python3 Code:
```python
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
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(nlogn)$
* 空间复杂度：不确定，取决于内置的排序算法
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/2593.find-score-of-an-array-after-marking-all-elements.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.