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与i1。重复此过程直到数组中所有元素都被标记。最后返回执行上述算法后的分数。示例 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^51 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和i1时当i 1原下标 0数组首元素时i-1 0落在额外开辟的哨兵位上不会越界当i n原下标 n-1数组尾元素时i1 n1同样落在哨兵位上。从而避免了在每个分支里写越界判断代码更简洁且安全。关键点用哈希表 / 布尔数组记录每个元素的访问标记状态排序后从小到大取未标记元素命中后更新左右邻居的访问状态访问标记数组左右各扩充一位哨兵简化边界处理取元素前必须先判断是否已访问已访问则跳过。代码实现Python3class Solution: def findScore(self, nums: List[int]) - int: ans 0 vis [False] * (len(nums) 2) # 保证下标不越界 for i, x in sorted(enumerate(nums, 1), keylambda p: p[1]): if not vis[i]: vis[i - 1] True vis[i 1] True # 标记相邻的两个元素 ans x return ans代码要点逐行拆解enumerate(nums, 1)为每个元素生成(下标, 值)对下标从 1 开始为哨兵位设计服务sorted(..., keylambda 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 原文反复揣摩并结合上述同类题目加深对该套路的理解。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考