价格范围内最高排名的 K 样物品

难度: Medium

给你一个下标从 0 开始的二维整数数组 grid ，它的大小为 m x n ，表示一个商店中物品的分布图。数组中的整数含义为：

0 表示无法穿越的一堵墙。
1 表示可以自由通过的一个空格子。
所有其他正整数表示该格子内的一样物品的价格。你可以自由经过这些格子。

从一个格子走到上下左右相邻格子花费 1 步。

同时给你一个整数数组 pricing 和 start ，其中 pricing = [low, high] 且 start = [row, col] ，表示你开始位置为 (row, col) ，同时你只对物品价格在 闭区间 [low, high] 之内的物品感兴趣。同时给你一个整数 k 。

你想知道给定范围内且 排名最高 的 k 件物品的位置。排名按照优先级从高到低的以下规则制定：

距离：定义为从 start 到一件物品的最短路径需要的步数（较近距离的排名更高）。
价格：较低价格的物品有更高优先级，但只考虑在给定范围之内的价格。
行坐标：较小行坐标的有更高优先级。
列坐标：较小列坐标的有更高优先级。

请你返回给定价格内排名最高的 k 件物品的坐标，将它们按照排名排序后返回。如果给定价格内少于 k 件物品，那么请将它们的坐标全部返回。

示例 1：

输入：grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
输出：[[0,1],[1,1],[2,1]]
解释：起点为 (0,0) 。
价格范围为 [2,5] ，我们可以选择的物品坐标为 (0,1)，(1,1)，(2,1) 和 (2,2) 。
这些物品的排名为：
- (0,1) 距离为 1
- (1,1) 距离为 2
- (2,1) 距离为 3
- (2,2) 距离为 4
所以，给定价格范围内排名最高的 3 件物品的坐标为 (0,1)，(1,1) 和 (2,1) 。

示例 2：

输入：grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2
输出：[[2,1],[1,2]]
解释：起点为 (2,3) 。
价格范围为 [2,3] ，我们可以选择的物品坐标为 (0,1)，(1,1)，(1,2) 和 (2,1) 。
这些物品的排名为： 
- (2,1) 距离为 2 ，价格为 2
- (1,2) 距离为 2 ，价格为 3
- (1,1) 距离为 3
- (0,1) 距离为 4
所以，给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (1,2) 。

示例 3：

输入：grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
输出：[[2,1],[2,0]]
解释：起点为 (0,0) 。
价格范围为 [2,3] ，我们可以选择的物品坐标为 (2,0) 和 (2,1) 。
这些物品的排名为：
- (2,1) 距离为 5
- (2,0) 距离为 6
所以，给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (2,0) 。
注意，k = 3 但给定价格范围内只有 2 件物品。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
0 <= grid[i][j] <= 10⁵
pricing.length == 2
2 <= low <= high <= 10⁵
start.length == 2
0 <= row <= m - 1
0 <= col <= n - 1
grid[row][col] > 0
1 <= k <= m * n

Submission

运行时间: 512 ms

内存: 51.9 MB

class Solution:
    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
        
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
        items = []  # 存储价格在范围内的物品的信息：(距离，价格，行坐标，列坐标)

        # 广度优先搜索
        queue = deque([(start[0], start[1], 0)])  # (行坐标，列坐标，距离)
        visited[start[0]][start[1]] = True
        while queue:
            x, y, dist = queue.popleft()
            if pricing[0] <= grid[x][y] <= pricing[1]:
                items.append((dist, grid[x][y], x, y))
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] != 0:
                    visited[nx][ny] = True
                    queue.append((nx, ny, dist + 1))

        # 按照题目要求的规则对物品进行排序
        items.sort()
        # 返回排名最高的k件物品的坐标，如果物品数少于k则返回所有物品坐标
        return [(x, y) for _, _, x, y in items[:k]]

Explain

此题解采用广度优先搜索（BFS）来寻找所有符合价格范围的物品，并计算从起始位置到每个物品的最短路径。首先，它初始化一个队列用以存放当前的位置和步数，并使用一个访问数组来防止重复访问。对于队列中的每个元素，算法检查其四个方向的邻居节点，若节点有效且未被访问过，则将其加入队列。同时，如果当前节点的值在给定的价格范围内，它将节点的位置和距离信息存入结果列表。完成搜索后，根据题目要求的顺序（距离、价格、行坐标、列坐标）对结果列表进行排序，最后选取前k个结果返回。

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

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

class Solution:
    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
        
        m, n = len(grid), len(grid[0])  # 获取网格的行数和列数
        visited = [[False] * n for _ in range(m)]  # 初始化访问标记数组
        directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]  # 可以前往的四个方向
        items = []  # 存储价格在范围内的物品的信息：(距离，价格，行坐标，列坐标)

        # 广度优先搜索
        queue = deque([(start[0], start[1], 0)])  # (行坐标，列坐标，距离)
        visited[start[0]][start[1]] = True
        while queue:
            x, y, dist = queue.popleft()
            if pricing[0] <= grid[x][y] <= pricing[1]:
                items.append((dist, grid[x][y], x, y))
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] != 0:
                    visited[nx][ny] = True
                    queue.append((nx, ny, dist + 1))

        # 按照题目要求的规则对物品进行排序
        items.sort()
        # 返回排名最高的k件物品的坐标，如果物品数少于k则返回所有物品坐标
        return [(x, y) for _, _, x, y in items[:k]]

Explore

在广度优先搜索（BFS）中，确认节点未被访问过是为了避免重复处理同一个节点，这样可以避免无限循环和资源浪费。确认节点不是墙（即grid[x][y] != 0）是因为墙代表不可通过的区域，不应该进入这样的节点。这两个条件确保了搜索的有效性和效率。

将距离作为排序的第一关键字是因为题目可能需要找出最容易到达的物品，即最短路径的物品。因此，距离较短意味着物品更容易获取，这通常是解决实际问题时的首要考虑因素。

题解中指出，如果找到的符合条件的物品数量少于k个，则返回所有找到的物品的坐标。这是在题解代码的最后部分通过`items[:k]`实现的，这里的切片操作将安全地返回不超过列表长度的元素，因此即使物品数少于k，也只会返回实际找到的物品。

在广度优先搜索中，使用队列来存储每个即将探索的节点及其对应的距离。具体地，初始化时将起始节点加入队列。在搜索过程中，从队列中移除（`popleft`）当前节点，并处理当前节点。如果当前节点的邻居有效且未被访问过，则将这些邻居节点及其距离加入（`append`）到队列的末尾。这种先进先出（FIFO）的特性使得BFS能够按层次依次处理节点。