图中最大星和

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

难度: Medium

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

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

星图 是给定图中的一个子图，它包含一个中心节点和 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 <= 105
  • -104 <= vals[i] <= 104
  • 0 <= edges.length <= min(n * (n - 1) / 2, 105)
  • edges[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • 0 <= k <= n - 1

Submission

运行时间: 180 ms

内存: 50.8 MB

class Solution:
    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:
        g = [[] for _ in vals]
        for a, b in edges:
            if vals[b] > 0:
                heapq.heappush(g[a], vals[b])
                if len(g[a]) > k:
                    heapq.heappop(g[a])
            if vals[a] > 0:
                heapq.heappush(g[b], vals[a])
                if len(g[b]) > k:
                    heapq.heappop(g[b])
        return max(v + sum(g[i]) for i, v in enumerate(vals))

Explain

该题解主要采用了贪心策略和优先队列（最小堆）来解决问题。首先，为每个节点维护一个优先队列（最小堆），用来存储该节点的所有邻居节点的值，但只保留值最大的k个邻居。这是因为我们想要最大化星和，所以只保留最大的k个邻居值。当遍历每条边时，我们将节点值为正的邻居节点的值添加到对应的优先队列中。如果队列的长度超过k，则移除最小的元素，确保队列中只保留k个最大的值。在构建完所有节点的优先队列后，我们计算每个节点作为中心，其星和的最大值，即节点本身的值加上其优先队列中所有值的和，最后返回所有节点的最大星和。

时间复杂度: O(m * log k + n * k)

空间复杂度: O(n * k)

class Solution:
    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:
        g = [[] for _ in vals]  # 为每个节点初始化一个最小堆
        for a, b in edges:  # 遍历每条边
            if vals[b] > 0:  # 仅当邻居节点的值大于0时考虑
                heapq.heappush(g[a], vals[b])  # 将节点b的值加入到节点a的堆中
                if len(g[a]) > k:  # 如果堆的大小超过k，则弹出最小元素
                    heapq.heappop(g[a])
            if vals[a] > 0:  # 同上，处理节点a对节点b的贡献
                heapq.heappush(g[b], vals[a])
                if len(g[b]) > k:
                    heapq.heappop(g[b])
        return max(v + sum(g[i]) for i, v in enumerate(vals))  # 计算每个节点作为中心的最大星和，并返回最大值

Explore

在此题解中，对于邻居节点值为0或负数的情况，我们选择不将这些值加入优先队列（最小堆）。这是因为我们的目标是最大化每个节点的星和，而星和的计算只考虑正值对总和的贡献。将值为0或负数的邻居加入堆中不仅无助于提升星和，反而可能占据堆中的有限空间（k个位置），导致不能保留更多的正值邻居，从而降低可能的最大星和。

这种处理方式基于题目定义的星和的计算方法，即一个节点的星和是该节点值和其最大的k个邻居值的总和。这里的关键是只考虑直接邻居的值对星和的贡献，而非邻居的邻居。这种定义下的计算方法是准确的，不会影响结果的正确性。忽略邻居的邻居情况是因为题目仅要求计算直接邻居的影响。

如果某个节点的邻居数量少于k个，我们仍然会把这些邻居（只要它们的值为正）的值添加到该节点的优先队列中，但这个队列中的元素数量将少于k个。在计算该节点的星和时，我们只将队列中存在的邻居值求和，加上节点本身的值。这意味着，即使邻居数量不足k个，我们也能正确处理并计算出该节点的星和。

贪心策略在选择保留k个最大邻居时主要目的是简化问题并尽可能地寻找局部最优解。这种策略可能确实忽略了一些可能的全局优化，比如考虑特定的图结构或特殊情况下的优化策略。然而，对于大多数情况，贪心策略提供了一个效率高且实现简单的解决方案。对于能否在特定条件下提前确定星和的最大值，这取决于具体问题的限制和附加条件，可能需要更复杂的算法或数据结构来实现更优的解决方案。