What is the greedy approach in the Maximum Star Sum of a Graph problem?

The greedy approach involves selecting the node with the largest value and choosing the top k neighbors that maximize the total sum of the star graph.

How do I know which neighbors to include in the star graph?

Include only the neighbors whose values positively contribute to the total sum of the graph. This is determined by sorting the neighbors by their value and selecting the top k.

What is a star graph in this context?

A star graph is a subgraph where one node acts as the center, and it connects to one or more neighbors, forming a star-like structure.

How does the Maximum Star Sum of a Graph relate to greedy algorithms?

The problem relies on greedy algorithms by selecting neighbors that maximize the sum, ensuring that only the most beneficial nodes are included in the final star graph.

What are the key challenges in solving the Maximum Star Sum of a Graph?

The main challenges include efficiently selecting the right neighbors, ensuring that only beneficial neighbors are included, and handling large graphs within time constraints.

#2497

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

图中最大星和

给你一个 n 个点的无向图，节点从 0 到 n - 1 编号。给你一个长度为 n 下标从 0 开始的整数数组 vals ，其中 vals[i] 表示第 i 个节点的值。同时给你一个二维整数数组 edges ，其中 edges[i] = [a i , b i ] 表示节点 a i 和 b i 之间有…

数组贪心图排序堆（优先队列）

题目描述

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

同时给你一个二维整数数组 edges ，其中 edges[i] = [a_i, b_i] 表示节点 a_i 和 b_i 之间有一条双向边。

星图是给定图中的一个子图，它包含一个中心节点和 0 个或更多个邻居。换言之，星图是给定图中一个边的子集，且这些边都有一个公共节点。

下图分别展示了有 3 个和 4 个邻居的星图，蓝色节点为中心节点。

星和定义为星图中所有节点值的和。

给你一个整数 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 的星图。

示例 2：

输入：vals = [-5], edges = [], k = 0
输出：-5
解释：只有一个星图，就是节点 0 自己。
所以我们返回 -5 。

提示：

n == vals.length
1 <= n <= 10⁵
-10⁴ <= vals[i] <= 10⁴
0 <= edges.length <= min(n * (n - 1) / 2, 10⁵)
edges[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i
0 <= k <= n - 1

lightbulb

解题思路

方法一：排序 + 模拟

我们先将输入的边集合转换成邻接表，其中 $g[i]$ 表示节点 $i$ 的邻居节点的值列表，且按照值的降序排列。

然后我们遍历每个节点 $i$ ，计算以 $i$ 为中心节点的星图的最大星和，即 $vals[i] + \sum_{j=0}^{k-1} g[i][j]$ ，并且更新最大星和。

最后返回最大星和即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ ，其中 $n$ 为节点数。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:
        g = defaultdict(list)
        for a, b in edges:
            if vals[b] > 0:
                g[a].append(vals[b])
            if vals[a] > 0:
                g[b].append(vals[a])
        for bs in g.values():
            bs.sort(reverse=True)
        return max(v + sum(g[i][:k]) for i, v in enumerate(vals))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should recognize that greedy choices and local optimization are key to maximizing the star sum.
question_mark
Look for understanding of graph traversal and how to handle neighbors efficiently without unnecessary computations.
question_mark
Candidates should demonstrate the ability to implement the greedy approach and validate the sum correctly.

warning

常见陷阱

外企场景

error
Forgetting that not all neighbors should be included—only those that increase the sum.
error
Overcomplicating the selection of neighbors or failing to efficiently sort and choose the top k neighbors.
error
Misunderstanding the problem constraints and attempting to include all neighbors instead of limiting the number.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing more than k neighbors to be selected may change the approach and solution complexity.
arrow_right_alt
Instead of maximizing the sum, trying to minimize it by selecting the least beneficial neighbors.
arrow_right_alt
Expanding to weighted graphs where edges also contribute to the sum would increase the complexity of the problem.

help

常见问题

外企场景

继续练习

#2542 最大子序列的分数 #2551 将珠子放入背包中 #2406 将区间分为最少组数