矩阵查询可获得的最大分数

标签: 广度优先搜索 并查集 数组 双指针 矩阵 排序 堆（优先队列）

难度: Hard

给你一个大小为 m x n 的整数矩阵 grid 和一个大小为 k 的数组 queries 。

找出一个大小为 k 的数组 answer ，且满足对于每个整数 queries[i] ，你从矩阵 左上角 单元格开始，重复以下过程：

  • 如果 queries[i] 严格 大于你当前所处位置单元格，如果该单元格是第一次访问，则获得 1 分，并且你可以移动到所有 4 个方向（上、下、左、右）上任一 相邻 单元格。
  • 否则，你不能获得任何分，并且结束这一过程。

在过程结束后，answer[i] 是你可以获得的最大分数。注意，对于每个查询，你可以访问同一个单元格 多次 。

返回结果数组 answer 。

示例 1：

输入：grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]
输出：[5,8,1]
解释：上图展示了每个查询中访问并获得分数的单元格。

示例 2：

输入：grid = [[5,2,1],[1,1,2]], queries = [3]
输出：[0]
解释：无法获得分数，因为左上角单元格的值大于等于 3 。

提示：

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 1000
  • 4 <= m * n <= 105
  • k == queries.length
  • 1 <= k <= 104
  • 1 <= grid[i][j], queries[i] <= 106

Submission

运行时间: 416 ms

内存: 26.9 MB

import heapq
class Solution:
    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
        m, n = len(grid), len(grid[0])
        ans = [0 for q in queries]
        priority_queue = [(grid[0][0], 0, 0)]
        grid[0][0] = -1
        max_q = max(queries)
        cnt = 0
        for j, q in sorted(enumerate(queries), key=lambda x: x[1]):
            while priority_queue and priority_queue[0][0] < q:
                dist, x, y = heapq.heappop(priority_queue)
                cnt += 1
                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    x_p, y_p = x + dx, y + dy
                    if x_p >= 0 and x_p < m and y_p >= 0 and y_p < n and grid[x_p][y_p] > 0:
                        heapq.heappush(priority_queue, (max(grid[x_p][y_p], dist), x_p, y_p))
                        grid[x_p][y_p] = -1
            ans[j] = cnt

        return ans

Explain

这个题解采用了优先队列（最小堆）的方式来实现。首先，初始化一个优先队列，将左上角的单元格作为起始点加入队列，并将其值标记为-1（已访问）。对于每个查询值，按照大小排序来处理。处理查询时，如果队列的顶部元素（当前值最小的元素）小于查询值，从队列中取出该元素，并探索其四个方向的相邻单元格。如果相邻单元格的值有效且未被访问，则将其加入队列，并将值设为-1。每次从队列中取出元素时，计数器递增，表示获得了分数。队列中的元素代表可以继续探索的单元格，只要其值小于当前查询值。最后，将计数器的值存入结果数组，该值即为当前查询所能获得的最大分数。

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

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

import heapq
class Solution:
    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
        m, n = len(grid), len(grid[0])
        ans = [0 for q in queries]
        priority_queue = [(grid[0][0], 0, 0)]  # 初始化优先队列，加入左上角单元格
        grid[0][0] = -1  # 标记为已访问
        max_q = max(queries)
        cnt = 0
        for j, q in sorted(enumerate(queries), key=lambda x: x[1]):  # 对查询排序
            while priority_queue and priority_queue[0][0] < q:  # 弹出所有小于当前查询值的元素
                dist, x, y = heapq.heappop(priority_queue)
                cnt += 1  # 增加得分
                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    x_p, y_p = x + dx, y + dy
                    if x_p >= 0 and x_p < m and y_p >= 0 and y_p < n and grid[x_p][y_p] > 0:  # 检查边界和是否已访问
                        heapq.heappush(priority_queue, (max(grid[x_p][y_p], dist), x_p, y_p))
                        grid[x_p][y_p] = -1  # 标记为已访问
            ans[j] = cnt  # 存储结果
        return ans

Explore

在处理查询之前进行排序是为了确保当我们从优先队列中移除元素时，这些元素的值都小于当前查询值。这样可以避免重复检查或重新插入已经处理过且大于某些查询值的元素。此外，排序可以保证我们逐步增加查询值，从而使得优先队列中只需要包含当前查询值或更小的值，这样可以减少每次查询时的操作数量，提高算法的效率。如果不进行排序，可能需要对每个查询重置整个程序状态或进行复杂的回溯，这将大大增加时间复杂度。

在此算法中，使用元素的值作为比较基准是有效的，因为这与问题的核心目标——处理小于当前查询值的所有元素——直接相关。这种方法确保了只处理那些必要的、符合当前查询条件的元素，从而维持了算法的效率。尽管如此，也可以考虑其他属性作为比较基准，如元素的位置或其在矩阵中的相对深度（即从起点到该点的步数），这些方法可能在处理具有特定空间或路径优先要求的不同问题时更有优势。然而，对于当前问题，值作为基准是最直接且有效的方法。

在这个上下文中，'有效'指的是单元格的值大于0且未被访问过。在这个算法中，一个被访问的单元格会被标记为-1，因此任何非负数的单元格都被认为是未被访问过的。这里的有效性确保了我们不会重复处理已经访问过的单元格，并且只处理那些可能对结果产生贡献的单元格（即值大于0的单元格）。