Medium

题目描述

给定一个由 n 个节点组成的无向图，节点编号从 0 到 n - 1。给你一个长度为 n 的 0 索引整数数组 vals，其中 vals[i] 表示第 i 个节点的值。

还给你一个二维整数数组 edges，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间存在一条无向边。

星形图是给定图的一个子图，它有一个中心节点，包含 0 个或多个邻居。换句话说，它是给定图的边的一个子集，使得所有边都有一个公共节点。

星形图的和是星形图中所有节点值的总和。

给定一个整数 k，返回包含最多 k 条边的星形图的最大星形和。

示例 1：

输入：vals = [1,2,3,4,10,-10,-20], edges = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]], k = 2
输出：16
解释：以节点 3 为中心，包含邻居 1 和 4 的星形图有最大星形和 16。

示例 2：

输入：vals = [-5], edges = [], k = 0
输出：-5
解释：只有一个可能的星形图，即节点 0 本身。

约束条件：

  • n == vals.length
  • 1 <= n <= 10^5
  • -10^4 <= vals[i] <= 10^4
  • 0 <= edges.length <= min(n * (n - 1) / 2, 10^5)
  • edges[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • 0 <= k <= n - 1

解题思路

这道题要求找到图中星形子图的最大和。星形图是以某个节点为中心，连接其部分或全部邻居的子图。

核心思路：

  1. 贪心策略：对于每个节点作为中心，我们应该选择其值最大的前 k 个邻居（只考虑正值邻居）
  2. 图构建：首先根据边列表构建邻接表
  3. 排序优化：对每个节点的邻居按值降序排列
  4. 最优选择：遍历每个节点，计算以该节点为中心的最大星形和

算法步骤：

  1. 构建图的邻接表表示
  2. 对每个节点的邻居列表按照节点值降序排序
  3. 对每个节点，贪心地选择最多 k 个值最大的邻居
  4. 计算每个可能的星形图和，取最大值

关键点：

  • 即使 k=0，每个单独的节点也是一个星形图
  • 只选择值为正数的邻居，负数邻居会减少总和
  • 对于邻居数少于 k 的节点，选择所有正值邻居

代码实现

class Solution {
public:
    int maxStarSum(vector<int>& vals, vector<vector<int>>& edges, int k) {
        int n = vals.size();
        vector<vector<int>> graph(n);
        
        // 构建邻接表
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        int maxSum = *max_element(vals.begin(), vals.end());
        
        // 遍历每个节点作为中心
        for (int i = 0; i < n; i++) {
            // 对邻居按值降序排序
            sort(graph[i].begin(), graph[i].end(), [&](int a, int b) {
                return vals[a] > vals[b];
            });
            
            int currentSum = vals[i];
            int count = 0;
            
            // 贪心选择最多k个最大值的邻居
            for (int neighbor : graph[i]) {
                if (count >= k) break;
                if (vals[neighbor] > 0) {
                    currentSum += vals[neighbor];
                    count++;
                } else {
                    break; // 由于已排序，后面都是非正数
                }
            }
            
            maxSum = max(maxSum, currentSum);
        }
        
        return maxSum;
    }
};

class Solution:
    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:
        n = len(vals)
        graph = [[] for _ in range(n)]
        
        # 构建邻接表
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        max_sum = max(vals)
        
        # 遍历每个节点作为中心
        for i in range(n):
            # 对邻居按值降序排序
            graph[i].sort(key=lambda x: vals[x], reverse=True)
            
            current_sum = vals[i]
            count = 0
            
            # 贪心选择最多k个最大值的邻居
            for neighbor in graph[i]:
                if count >= k:
                    break
                if vals[neighbor] > 0:
                    current_sum += vals[neighbor]
                    count += 1
                else:
                    break  # 由于已排序，后面都是非正数
            
            max_sum = max(max_sum, current_sum)
        
        return max_sum

public class Solution {
    public int MaxStarSum(int[] vals, int[][] edges, int k) {
        int n = vals.Length;
        List<int>[] graph = new List<int>[n];
        
        // 初始化邻接表
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        // 构建邻接表
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        int maxSum = vals.Max();
        
        // 遍历每个节点作为中心
        for (int i = 0; i < n; i++) {
            // 对邻居按值降序排序
            graph[i].Sort((a, b) => vals[b].CompareTo(vals[a]));
            
            int currentSum = vals[i];
            int count = 0;
            
            // 贪心选择最多k个最大值的邻居
            foreach (int neighbor in graph[i]) {
                if (count >= k) break;
                if (vals[neighbor] > 0) {
                    currentSum += vals[neighbor];
                    count++;
                } else {
                    break; // 由于已排序，后面都是非正数
                }
            }
            
            maxSum = Math.Max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

var maxStarSum = function(vals, edges, k) {
    const n = vals.length;
    const graph = Array.from({ length: n }, () => []);
    
    // 构建邻接表
    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a);
    }
    
    let maxSum = Math.max(...vals);
    
    // 遍历每个节点作为中心
    for (let i = 0; i < n; i++) {
        // 对邻居按值降序排序
        graph[i].sort((a, b) => vals[b] - vals[a]);
        
        let currentSum = vals[i];
        let count = 0;
        
        // 贪心选择最多k个最大值的邻居
        for (const neighbor of graph[i]) {
            if (count >= k) break;
            if (vals[neighbor] > 0) {
                currentSum += vals[neighbor];
                count++;
            } else {
                break; // 由于已排序，后面都是非正数
            }
        }
        
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n + m + n·d·log d)，其中 n 是节点数，m 是边数，d 是最大度数
空间复杂度O(n + m)

说明：

  • 构建邻接表需要 O(n + m) 时间
  • 对每个节点的邻居排序需要 O(d·log d) 时间，总共 O(n·d·log d)
  • 最坏情况下 d 可达 n-1，但平均情况下远小于 n
  • 空间复杂度主要用于存储邻接表

相关题目