🏆 价格范围内最高排名的 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件物品，那么请将它们的坐标全部返回。
📋 代码模板
java
class Solution {
public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
}
}typescript
function highestRankedKItems(grid: number[][], pricing: number[], start: number[], k: number): number[][] {
}💡 提示
🚀 示例
🖊️ 题解
可惜没有如果
java
class Solution {
private final static int[][] DIRS = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing
, int[] start, int k) {
int m = grid.length, n = grid[0].length;
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
List<int[]> list = new ArrayList<>();
queue.offer(start);
visited[start[0]][start[1]] = true;
int startPrice = grid[start[0]][start[1]];
if (startPrice >= pricing[0] && startPrice <= pricing[1]) {
list.add(start);
}
List<List<Integer>> ans = new ArrayList<>();
while (!queue.isEmpty()) {
list.sort((pos1, pos2) -> {
int price1 = grid[pos1[0]][pos1[1]], price2 = grid[pos2[0]][pos2[1]];
if (price1 != price2) {
return price1 - price2;
}
if (pos1[0] != pos2[0]) {
return pos1[0] - pos2[0];
}
return pos1[1] - pos2[1];
});
for (int i = 0; i < list.size() && ans.size() < k; i++) {
int[] pos = list.get(i);
List<Integer> r = new ArrayList<>();
r.add(pos[0]);
r.add(pos[1]);
ans.add(r);
}
if (ans.size() == k) {
break;
}
list.clear();
int size = queue.size();
while (size > 0) {
int[] cell = queue.poll();
int originalI = cell[0], originalJ = cell[1];
for (int d = 0; d < 4; d++) {
int i = originalI + DIRS[d][0], j = originalJ + DIRS[d][1];
if (i < 0 || i > m - 1 || j < 0 || j > n - 1 ||
grid[i][j] == 0 || visited[i][j]) {
continue;
}
queue.offer(new int[]{i, j});
visited[i][j] = true;
if (grid[i][j] >= pricing[0] && grid[i][j] <= pricing[1]) {
list.add(new int[]{i, j});
}
}
size--;
}
}
return ans;
}
}typescript
const DIRS: number[][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
function highestRankedKItems(grid: number[][], pricing: number[]
, start: number[], k: number): number[][] {
const m = grid.length, n = grid[0].length;
const visited: boolean[][] = Array.from({ length: m }, () => Array(n).fill(false));
const queue: number[][] = [];
const list: number[][] = [], ans: number[][] = [];
const startPrice = grid[start[0]][start[1]];
queue.push(start);
visited[start[0]][start[1]] = true;
if (startPrice >= pricing[0] && startPrice <= pricing[1]) {
list.push(start);
}
while (queue.length > 0) {
list.sort((pos1, pos2) => {
const price1 = grid[pos1[0]][pos1[1]], price2 = grid[pos2[0]][pos2[1]];
if (price1 != price2) {
return price1 - price2;
}
if (pos1[0] != pos2[0]) {
return pos1[0] - pos2[0];
}
return pos1[1] - pos2[1];
})
for (let i = 0; i < list.length && ans.length < k; i++) {
ans.push(list[i]);
}
if (ans.length == k) {
break;
}
list.splice(0, list.length);
let size = queue.length;
while (size > 0) {
const cell: number[] = queue.shift()!;
const originalI = cell[0], originalJ = cell[1];
for (let d = 0; d < 4; d++) {
const i = originalI + DIRS[d][0], j = originalJ + DIRS[d][1];
if (i < 0 || i > m - 1 || j < 0 || j > n - 1 ||
grid[i][j] == 0 || visited[i][j]) {
continue;
}
queue.push([i, j]);
visited[i][j] = true;
if (grid[i][j] >= pricing[0] && grid[i][j] <= pricing[1]) {
list.push([i, j]);
}
}
size--;
}
}
return ans;
}