价格范围内最高排名的 K 样物品
难度:
标签:
题目描述
给你一个下标从 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.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 1050 <= grid[i][j] <= 105pricing.length == 22 <= low <= high <= 105start.length == 20 <= row <= m - 10 <= col <= n - 1grid[row][col] > 01 <= k <= m * n
代码结果
运行时间: 512 ms, 内存: 51.9 MB
/* 思路：
1. 使用流 (Stream) 收集所有符合价格范围的物品。
2. 对物品按距离、价格、行坐标、列坐标排序。
3. 返回前 k 个物品的坐标。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public List<int[]> highestRankedItems(int[][] grid, int[] pricing, int[] start, int k) {
int m = grid.length, n = grid[0].length;
int low = pricing[0], high = pricing[1];
int startRow = start[0], startCol = start[1];
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
List<int[]> items = new ArrayList<>();
queue.add(new int[]{startRow, startCol, 0}); // {row, col, distance}
visited[startRow][startCol] = true;
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int row = curr[0], col = curr[1], dist = curr[2];
if (grid[row][col] >= low && grid[row][col] <= high) {
items.add(new int[]{row, col, dist});
}
for (int[] dir : directions) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] != 0 && !visited[newRow][newCol]) {
queue.add(new int[]{newRow, newCol, dist + 1});
visited[newRow][newCol] = true;
}
}
}
return items.stream()
.sorted((a, b) -> {
if (a[2] != b[2]) return Integer.compare(a[2], b[2]); // Compare distance
if (grid[a[0]][a[1]] != grid[b[0]][b[1]]) return Integer.compare(grid[a[0]][a[1]], grid[b[0]][b[1]]); // Compare price
if (a[0] != b[0]) return Integer.compare(a[0], b[0]); // Compare row
return Integer.compare(a[1], b[1]); // Compare column
})
.limit(k)
.map(item -> new int[]{item[0], item[1]})
.collect(Collectors.toList());
}
}解释
方法:
此题解采用广度优先搜索（BFS）来寻找所有符合价格范围的物品，并计算从起始位置到每个物品的最短路径。首先，它初始化一个队列用以存放当前的位置和步数，并使用一个访问数组来防止重复访问。对于队列中的每个元素，算法检查其四个方向的邻居节点，若节点有效且未被访问过，则将其加入队列。同时，如果当前节点的值在给定的价格范围内，它将节点的位置和距离信息存入结果列表。完成搜索后，根据题目要求的顺序（距离、价格、行坐标、列坐标）对结果列表进行排序，最后选取前k个结果返回。
时间复杂度:
O(m*n + L log L)
空间复杂度:
O(m*n + L)
代码细节讲解
🦆
为什么在检查节点是否有效时，需要同时确认`节点未被访问过`和`不是墙`？
▷🦆
在将符合价格范围的物品信息添加到结果列表时，为何选择将距离作为排序的第一关键字？
▷🦆
如何处理当找到的符合条件的物品数量少于k个时的情况？题解中是否有说明返回值的具体内容？
▷🦆
在广度优先搜索中，队列的使用是如何实现的，具体是如何添加和移除元素的？
▷