LeetCode 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.
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 <= 105
1 <= nums[i] <= 106
这里面最主要的是如何定义优先队列的排序规则,
这个规则定义好之后,用一个数组记录被访问过的元素即可。
属于新知识,学习到了。
Runtime: 267 ms, faster than 40.49% of Java online submissions for Find Score of an Array After Marking All Elements.
Memory Usage: 60.6 MB, less than 25.56% of Java online submissions for Find Score of an Array After Marking All Elements.