Medium

题目描述

给你一个由正整数组成的数组 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，我们选择最左边的那个，所以我们标记下标为 0 的那个和它的右相邻元素：[2,3,5,1,3,2]。
- 2 是唯一剩下的未标记元素，所以我们标记它：[2,3,5,1,3,2]。
我们的分数是 1 + 2 + 2 = 5。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

解题思路

这道题的核心思路是模拟题目描述的过程，关键在于如何高效地找到最小的未标记元素。

基本思路：

  1. 我们需要维护一个数据结构来快速找到最小的未标记元素
  2. 当选中一个元素后，需要标记该元素及其相邻元素
  3. 重复直到所有元素都被标记

优化方案： 使用优先队列（最小堆）来维护所有元素，按值和索引排序。每个元素存储为 (值, 索引) 的形式，这样能保证值小的优先，值相同时索引小的优先。

算法步骤：

  1. 将所有元素及其索引放入最小堆
  2. 使用布尔数组标记已被标记的元素
  3. 从堆顶取出最小元素，如果该元素未被标记：
    • 将其值加入分数
    • 标记该元素及其相邻元素
  4. 重复步骤3直到堆为空

这种方法避免了每次遍历数组找最小值，时间复杂度较优。

代码实现

class Solution {
public:
    long long findScore(vector<int>& nums) {
        int n = nums.size();
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<bool> marked(n, false);
        
        // 将所有元素加入优先队列
        for (int i = 0; i < n; i++) {
            pq.push({nums[i], i});
        }
        
        long long score = 0;
        
        while (!pq.empty()) {
            auto [val, idx] = pq.top();
            pq.pop();
            
            // 如果已经被标记，跳过
            if (marked[idx]) continue;
            
            // 加入分数
            score += val;
            
            // 标记当前元素和相邻元素
            marked[idx] = true;
            if (idx > 0) marked[idx - 1] = true;
            if (idx < n - 1) marked[idx + 1] = true;
        }
        
        return score;
    }
};

class Solution:
    def findScore(self, nums: List[int]) -> int:
        import heapq
        
        n = len(nums)
        # 创建最小堆，存储 (值, 索引)
        heap = [(nums[i], i) for i in range(n)]
        heapq.heapify(heap)
        
        marked = [False] * n
        score = 0
        
        while heap:
            val, idx = heapq.heappop(heap)
            
            # 如果已经被标记，跳过
            if marked[idx]:
                continue
            
            # 加入分数
            score += val
            
            # 标记当前元素和相邻元素
            marked[idx] = True
            if idx > 0:
                marked[idx - 1] = True
            if idx < n - 1:
                marked[idx + 1] = True
        
        return score

public class Solution {
    public long FindScore(int[] nums) {
        int n = nums.Length;
        var pq = new PriorityQueue<(int val, int idx), (int val, int idx)>();
        bool[] marked = new bool[n];
        
        // 将所有元素加入优先队列
        for (int i = 0; i < n; i++) {
            pq.Enqueue((nums[i], i), (nums[i], i));
        }
        
        long score = 0;
        
        while (pq.Count > 0) {
            var (val, idx) = pq.Dequeue();
            
            // 如果已经被标记，跳过
            if (marked[idx]) continue;
            
            // 加入分数
            score += val;
            
            // 标记当前元素和相邻元素
            marked[idx] = true;
            if (idx > 0) marked[idx - 1] = true;
            if (idx < n - 1) marked[idx + 1] = true;
        }
        
        return score;
    }
}

var findScore = function(nums) {
    const n = nums.length;
    // 创建元素数组并排序
    const elements = nums.map((val, idx) => [val, idx])
                        .sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    
    const marked = new Array(n).fill(false);
    let score = 0;
    
    for (const [val, idx] of elements) {
        // 如果已经被标记，跳过
        if (marked[idx]) continue;
        
        // 加入分数
        score += val;
        
        // 标记当前元素和相邻元素
        marked[idx] = true;
        if (idx > 0) marked[idx - 1] = true;
        if (idx < n - 1) marked[idx + 1] = true;
    }
    
    return score;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
优先队列解法O(n log n)O(n)

时间复杂度分析：

  • 构建优先队列需要 O(n log n) 时间
  • 每次从队列中取出元素需要 O(log n) 时间，最多取出 n 个元素
  • 总时间复杂度为 O(n log n)

空间复杂度分析：

  • 优先队列存储 n 个元素，需要 O(n) 空间
  • 标记数组需要 O(n) 空间
  • 总空间复杂度为 O(n)

相关题目