You are given an array nums consisting of positive integers.
Starting with score = 0, apply the following algorithm:
- Choose the smallest integer of the array that is not marked. If there is a tie, choose the one with the smallest index.
- Add the value of the chosen integer to
score. - Mark the chosen element and its two adjacent elements if they exist.
- Repeat until all the array elements are marked.
Return the score you get after applying the above algorithm.
Example 1:
Input: nums = [2,1,3,4,5,2] Output: 7 Explanation: We mark the elements as follows: - 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,1,3,4,5,2]. - 2 is the smallest unmarked element, so we mark it and its left adjacent element: [2,1,3,4,5,2]. - 4 is the only remaining unmarked element, so we mark it: [2,1,3,4,5,2]. Our score is 1 + 2 + 4 = 7.
Example 2:
Input: nums = [2,3,5,1,3,2] Output: 5 Explanation: We mark the elements as follows: - 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,3,5,1,3,2]. - 2 is the smallest unmarked element, since there are two of them, we choose the left-most one, so we mark the one at index 0 and its right adjacent element: [2,3,5,1,3,2]. - 2 is the only remaining unmarked element, so we mark it: [2,3,5,1,3,2]. Our score is 1 + 2 + 2 = 5.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 106
class Solution:
def findScore(self, nums: List[int]) -> int:
n = len(nums)
vis = [False] * n
q = [(x, i) for i, x in enumerate(nums)]
heapify(q)
ans = 0
while q:
x, i = heappop(q)
ans += x
vis[i] = True
for j in (i - 1, i + 1):
if 0 <= j < n:
vis[j] = True
while q and vis[q[0][1]]:
heappop(q)
return ansclass Solution:
def findScore(self, nums: List[int]) -> int:
n = len(nums)
vis = [False] * (n + 2)
idx = sorted(range(n), key=lambda i: (nums[i], i))
ans = 0
for i in idx:
if not vis[i + 1]:
ans += nums[i]
vis[i] = vis[i + 2] = True
return ansclass Solution {
public long findScore(int[] nums) {
int n = nums.length;
boolean[] vis = new boolean[n];
PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
for (int i = 0; i < n; ++i) {
q.offer(new int[] {nums[i], i});
}
long ans = 0;
while (!q.isEmpty()) {
var p = q.poll();
ans += p[0];
vis[p[1]] = true;
for (int j : List.of(p[1] - 1, p[1] + 1)) {
if (j >= 0 && j < n) {
vis[j] = true;
}
}
while (!q.isEmpty() && vis[q.peek()[1]]) {
q.poll();
}
}
return ans;
}
}class Solution {
public long findScore(int[] nums) {
int n = nums.length;
boolean[] vis = new boolean[n + 2];
Integer[] idx = new Integer[n];
for (int i = 0; i < n; ++i) {
idx[i] = i;
}
Arrays.sort(idx, (i, j) -> nums[i] - nums[j]);
long ans = 0;
for (int i : idx) {
if (!vis[i + 1]) {
ans += nums[i];
vis[i] = true;
vis[i + 2] = true;
}
}
return ans;
}
}class Solution {
public:
long long findScore(vector<int>& nums) {
int n = nums.size();
vector<bool> vis(n);
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> q;
for (int i = 0; i < n; ++i) {
q.emplace(nums[i], i);
}
long long ans = 0;
while (!q.empty()) {
auto [x, i] = q.top();
q.pop();
ans += x;
vis[i] = true;
if (i + 1 < n) {
vis[i + 1] = true;
}
if (i - 1 >= 0) {
vis[i - 1] = true;
}
while (!q.empty() && vis[q.top().second]) {
q.pop();
}
}
return ans;
}
};class Solution {
public:
long long findScore(vector<int>& nums) {
int n = nums.size();
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j) {
return nums[i] < nums[j] || (nums[i] == nums[j] && i < j);
});
long long ans = 0;
vector<bool> vis(n + 2);
for (int i : idx) {
if (!vis[i + 1]) {
ans += nums[i];
vis[i] = vis[i + 2] = true;
}
}
return ans;
}
};func findScore(nums []int) (ans int64) {
h := hp{}
for i, x := range nums {
heap.Push(&h, pair{x, i})
}
n := len(nums)
vis := make([]bool, n)
for len(h) > 0 {
p := heap.Pop(&h).(pair)
x, i := p.x, p.i
ans += int64(x)
vis[i] = true
for _, j := range []int{i - 1, i + 1} {
if j >= 0 && j < n {
vis[j] = true
}
}
for len(h) > 0 && vis[h[0].i] {
heap.Pop(&h)
}
}
return
}
type pair struct{ x, i int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].x < h[j].x || (h[i].x == h[j].x && h[i].i < h[j].i) }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }func findScore(nums []int) (ans int64) {
n := len(nums)
idx := make([]int, n)
for i := range idx {
idx[i] = i
}
sort.Slice(idx, func(i, j int) bool {
i, j = idx[i], idx[j]
return nums[i] < nums[j] || (nums[i] == nums[j] && i < j)
})
vis := make([]bool, n+2)
for _, i := range idx {
if !vis[i+1] {
ans += int64(nums[i])
vis[i], vis[i+2] = true, true
}
}
return
}interface pair {
x: number;
i: number;
}
function findScore(nums: number[]): number {
const q = new PriorityQueue({
compare: (a: pair, b: pair) => (a.x === b.x ? a.i - b.i : a.x - b.x),
});
const n = nums.length;
const vis: boolean[] = new Array(n).fill(false);
for (let i = 0; i < n; ++i) {
q.enqueue({ x: nums[i], i });
}
let ans = 0;
while (!q.isEmpty()) {
const { x, i } = q.dequeue()!;
if (vis[i]) {
continue;
}
ans += x;
vis[i] = true;
if (i - 1 >= 0) {
vis[i - 1] = true;
}
if (i + 1 < n) {
vis[i + 1] = true;
}
while (!q.isEmpty() && vis[q.front()!.i]) {
q.dequeue();
}
}
return ans;
}function findScore(nums: number[]): number {
const n = nums.length;
const idx: number[] = new Array(n);
for (let i = 0; i < n; ++i) {
idx[i] = i;
}
idx.sort((i, j) => (nums[i] == nums[j] ? i - j : nums[i] - nums[j]));
const vis: boolean[] = new Array(n + 2).fill(false);
let ans = 0;
for (const i of idx) {
if (!vis[i + 1]) {
ans += nums[i];
vis[i] = true;
vis[i + 2] = true;
}
}
return ans;
}