2593. Find Score of an Array After Marking All Elements

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.

c++

class Solution {
public:
    long long findScore(vector<int>& nums) {
        long long res = 0;
        vector<int> mark(nums.size());
        priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> q, exc;
        for(int i = 0; i < nums.size(); i++) q.push({nums[i], i});
        while(q.size()) {
            auto [x, idx] = q.top(); q.pop();
            mark[idx] = true;
            res += x;
            if(idx - 1 >= 0 and !mark[idx-1]) {
                mark[idx-1] = true;
                exc.push({nums[idx-1], idx-1});
            }
            if(idx + 1 < nums.size() and !mark[idx+1]) {
                mark[idx+1] = true;
                exc.push({nums[idx+1], idx+1});
            }
            while(exc.size() and exc.top() == q.top()) {
                exc.pop();
                q.pop();
            }
        }
        return res;
    }
};

c++

class Solution {
public:
    long long findScore(vector<int>& nums) {
        long long res = 0;
        vector<int> mark(nums.size());
        priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> q;
        for(int i = 0; i < nums.size(); i++) q.push({nums[i], i});
        while(q.size()) {
            while(q.size() and mark[q.top().second]) q.pop();
            if(q.empty()) break;
            auto [x, idx] = q.top(); q.pop();
            mark[idx] = true;
            res += x;
            if(idx - 1 >= 0) mark[idx-1] = true;
            if(idx + 1 < nums.size()) mark[idx+1] = true;
        }
        return res;
    }
};