欢迎光临散文网 会员登陆 & 注册

LeetCode 2593. Find Score of an Array After Marking All Elements

2023-04-11 09:42 作者:您是打尖儿还是住店呢  | 我要投稿

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.



LeetCode 2593. Find Score of an Array After Marking All Elements的评论 (共 条)

分享到微博请遵守国家法律