What is the key pattern in K Highest Ranked Items Within a Price Range?

The key pattern is array plus breadth-first search. BFS computes the shortest distance from the start in an unweighted grid, and that distance is the first ranking field, so traversal order matters before sorting the final candidates.

Why is BFS better than DFS for LeetCode 2146?

DFS can reach an item through a longer path before a shorter one, so it does not naturally produce minimum distance. Since this problem ranks items by shortest distance first, BFS is the correct fit.

Do I need to sort the whole grid?

No. Only reachable cells discovered by BFS can matter, and only cells with prices inside the range become candidates. Sorting the entire grid wastes work and can mix in blocked or unreachable positions.

Can I stop BFS as soon as I collect k items?

Not safely in the general case. You may find k items at one distance, but more items at that same distance could still appear later in the BFS layer and beat some of your current picks by lower price, row, or column.

What tie breakers matter after distance?

After smaller distance, prefer lower price, then smaller row, then smaller column. Missing even one of these tie breakers will fail hidden cases where multiple reachable items appear in the same BFS layer.

#2146

Medium

auto_awesome图·搜索

LeetCode 题解工作台

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

给你一个下标从 0 开始的二维整数数组 grid ，它的大小为 m x n ，表示一个商店中物品的分布图。数组中的整数含义为： 0 表示无法穿越的一堵墙。 1 表示可以自由通过的一个空格子。所有其他正整数表示该格子内的一样物品的价格。你可以自由经过这些格子。从一个格子走到上下左右相邻格子花费 1…

数组广度优先搜索排序堆（优先队列）矩阵

题目描述

给你一个下标从 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

lightbulb

解题思路

方法一：BFS + 排序

我们可以从 $(\textit{row}, \textit{col})$ 出发，使用广度优先搜索找到所有价格在 $[\textit{low}, \textit{high}]$ 范围内的物品，将这些物品的距离、价格、行坐标和列坐标存入数组 $\textit{pq}$ 中。

最后对 $\textit{pq}$ 按照距离、价格、行坐标和列坐标的顺序排序，取前 $k$ 个物品的坐标返回。

时间复杂度 $O(m \times n \times \log (m \times n))$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是二维数组 $\textit{grid}$ 的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

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])
        row, col = start
        low, high = pricing
        q = deque([(row, col)])
        pq = []
        if low <= grid[row][col] <= high:
            pq.append((0, grid[row][col], row, col))
        grid[row][col] = 0
        dirs = (-1, 0, 1, 0, -1)
        step = 0
        while q:
            step += 1
            for _ in range(len(q)):
                x, y = q.popleft()
                for a, b in pairwise(dirs):
                    nx, ny = x + a, y + b
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:
                        if low <= grid[nx][ny] <= high:
                            pq.append((step, grid[nx][ny], nx, ny))
                        grid[nx][ny] = 0
                        q.append((nx, ny))
        pq.sort()
        return [list(x[2:]) for x in pq[:k]]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They expect you to notice that shortest path on an unweighted grid means BFS, not Dijkstra or DFS.
question_mark
They are checking whether you can preserve the exact rank order: distance, price, row, then column.
question_mark
They want a solution that filters unreachable items naturally instead of scanning and ranking the whole matrix blindly.

warning

常见陷阱

外企场景

error
Sorting by price before distance gives the wrong answer because this problem ranks by BFS depth first.
error
Marking visited after popping instead of after pushing can enqueue the same cell multiple times and bloat the search.
error
Treating every positive cell as a valid answer is wrong because value 1 is walkable space, not a priced item in range unless the range includes 1, which it never does here since low is at least 2.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Keep only the best k items in a max-heap while running BFS instead of sorting every candidate at the end.
arrow_right_alt
Return the ranked item values as well as coordinates, which adds output formatting but keeps the same BFS ranking logic.
arrow_right_alt
Change movement rules to eight directions or weighted steps, which would break plain BFS and require a different shortest-path method.

help

常见问题

外企场景

继续练习

#2503 矩阵查询可获得的最大分数 #2290 到达角落需要移除障碍物的最小数目 #1878 矩阵中最大的三个菱形和