class Solution {
public:
long long findScore(vector<int>& nums) {
}
};
6351. 标记所有元素后数组的分数
给你一个数组 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 <= 1051 <= nums[i] <= 106原站题解
golang 解法, 执行用时: 228 ms, 内存消耗: 10.2 MB, 提交时间: 2023-03-19 22:15:03
func findScore(nums []int) (ans int64) {
type pair struct{ v, i int }
a := make([]pair, len(nums))
for i, x := range nums {
a[i] = pair{x, i + 1} // +1 保证下面 for 循环下标不越界
}
sort.Slice(a, func(i, j int) bool {
a, b := a[i], a[j]
return a.v < b.v || a.v == b.v && a.i < b.i
})
vis := make([]bool, len(nums)+2) // 保证下标不越界
for _, p := range a {
if !vis[p.i] {
vis[p.i-1] = true
vis[p.i+1] = true // 标记相邻的两个元素
ans += int64(p.v)
}
}
return
}
cpp 解法, 执行用时: 304 ms, 内存消耗: 86.9 MB, 提交时间: 2023-03-19 22:14:49
class Solution {
public:
long long findScore(vector<int> &nums) {
int n = nums.size(), ids[n];
iota(ids, ids + n, 0);
stable_sort(ids, ids + n, [&](int i, int j) {
return nums[i] < nums[j];
});
long long ans = 0;
bool vis[n + 2]; // 保证下标不越界
memset(vis, 0, sizeof(vis));
for (int i : ids)
if (!vis[i + 1]) {
vis[i] = vis[i + 2] = true;
ans += nums[i];
}
return ans;
}
};
java 解法, 执行用时: 108 ms, 内存消耗: 58.5 MB, 提交时间: 2023-03-19 22:14:37
class Solution {
public long findScore(int[] nums) {
int n = nums.length;
var ids = new Integer[n];
for (int i = 0; i < n; ++i) ids[i] = i;
Arrays.sort(ids, (i, j) -> nums[i] - nums[j]);
long ans = 0;
var vis = new boolean[n + 2]; // 保证下标不越界
for (int i : ids)
if (!vis[i + 1]) {
vis[i] = vis[i + 2] = true;
ans += nums[i];
}
return ans;
}
}
python3 解法, 执行用时: 316 ms, 内存消耗: 36.3 MB, 提交时间: 2023-03-19 22:14:26
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