题目描述
给你一个数组 nums
,它包含若干正整数。
一开始分数 score = 0
,请你按照下面算法求出最后分数:
- 从数组中选择最小且没有被标记的整数。如果有相等元素,选择下标最小的一个。
- 将选中的整数加到
score
中。 - 标记 被选中元素,如果有相邻元素,则同时标记 与它相邻的两个元素。
- 重复此过程直到数组中所有元素都被标记。
请你返回执行上述算法后最后的分数。
样例
输入: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。
输入: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
算法
(堆) $O(n \log n)$
- 建立一个小跟堆,并维护一个标记数组。
- 每次从堆中取出最小值,如果这个位置已经被标记,则忽略。
- 如果没有被标记,则累加答案,并标记相邻位置。
- 直到堆为空。
时间复杂度
- 建堆后,每个位置出堆一次,故时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储堆和标记数组。
C++ 代码
#define LL long long
#define PII pair<int, int>
class Solution {
public:
LL findScore(vector<int>& nums) {
priority_queue<PII, vector<PII>, greater<PII>> heap;
const int n = nums.size();
for (int i = 0; i < n; i++)
heap.push(make_pair(nums[i], i));
vector<bool> mark(n, false);
LL ans = 0;
while (!heap.empty()) {
PII top = heap.top();
heap.pop();
if (mark[top.second])
continue;
ans += top.first;
if (top.second > 0)
mark[top.second - 1] = true;
if (top.second < n - 1)
mark[top.second + 1] = true;
}
return ans;
}
};
爱了