2146. 价格范围内 K 个最高排名的物品

Medium

题目描述

给你一个大小为 m x n 的整数数组 grid ，表示商店中物品的分布图。数组中的整数含义如下：

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]]

示例 3：

输入：grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
输出：[[2,1],[2,0]]

提示：

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

解题思路

这道题需要找到价格范围内排名最高的 k 个物品，排名规则按距离、价格、行、列的优先级排序。

解题思路：

BFS 计算距离：从起始点开始进行广度优先搜索，计算到每个可达位置的最短距离。由于 BFS 的特性，先访问到的位置距离更近。
收集符合条件的物品：在 BFS 过程中，当遇到价格在给定范围内的物品时，将其位置、距离、价格等信息保存下来。
排序获取前k个：根据题目要求的排名规则对所有符合条件的物品进行排序：
- 首先按距离升序
- 距离相同时按价格升序
- 价格相同时按行坐标升序
- 行坐标相同时按列坐标升序
返回结果：取前 k 个物品的坐标作为答案。

算法优化：

使用 BFS 确保找到的是最短距离
在 BFS 过程中就筛选符合价格条件的物品，避免遍历所有位置
利用 BFS 的层次遍历特性，天然按距离有序

代码实现

class Solution {
public:
    vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int k) {
        int m = grid.size(), n = grid[0].size();
        int low = pricing[0], high = pricing[1];
        
        queue<pair<int, int>> q;
        vector<vector<int>> dist(m, vector<int>(n, -1));
        vector<vector<int>> items;
        
        q.push({start[0], start[1]});
        dist[start[0]][start[1]] = 0;
        
        // Check starting position
        if (grid[start[0]][start[1]] >= low && grid[start[0]][start[1]] <= high) {
            items.push_back({0, grid[start[0]][start[1]], start[0], start[1]});
        }
        
        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            
            for (int i = 0; i < 4; i++) {
                int nx = x + dirs[i][0];
                int ny = y + dirs[i][1];
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && 
                    grid[nx][ny] > 0 && dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                    
                    if (grid[nx][ny] >= low && grid[nx][ny] <= high) {
                        items.push_back({dist[nx][ny], grid[nx][ny], nx, ny});
                    }
                }
            }
        }
        
        sort(items.begin(), items.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[0] != b[0]) return a[0] < b[0]; // distance
            if (a[1] != b[1]) return a[1] < b[1]; // price
            if (a[2] != b[2]) return a[2] < b[2]; // row
            return a[3] < b[3]; // col
        });
        
        vector<vector<int>> result;
        for (int i = 0; i < min(k, (int)items.size()); i++) {
            result.push_back({items[i][2], items[i][3]});
        }
        
        return result;
    }
};

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])
        low, high = pricing
        
        queue = deque([(start[0], start[1])])
        dist = [[-1] * n for _ in range(m)]
        dist[start[0]][start[1]] = 0
        items = []
        
        # Check starting position
        if low <= grid[start[0]][start[1]] <= high:
            items.append((0, grid[start[0]][start[1]], start[0], start[1]))
        
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while queue:
            x, y = queue.popleft()
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0 and dist[nx][ny] == -1:
                    dist[nx][ny] = dist[x][y] + 1
                    queue.append((nx, ny))
                    
                    if low <= grid[nx][ny] <= high:
                        items.append((dist[nx][ny], grid[nx][ny], nx, ny))
        
        # Sort by distance, price, row, col
        items.sort()
        
        # Return first k items' coordinates
        return [[item[2], item[3]] for item in items[:k]]

public class Solution {
    public IList<IList<int>> HighestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
        int m = grid.Length, n = grid[0].Length;
        int low = pricing[0], high = pricing[1];
        
        var queue = new Queue<(int, int)>();
        var dist = new int[m][];
        for (int i = 0; i < m; i++) {
            dist[i] = new int[n];
            Array.Fill(dist[i], -1);
        }
        
        var items = new List<(int distance, int price, int row, int col)>();
        
        queue.Enqueue((start[0], start[1]));
        dist[start[0]][start[1]] = 0;
        
        // Check starting position
        if (grid[start[0]][start[1]] >= low && grid[start[0]][start[1]] <= high) {
            items.Add((0, grid[start[0]][start[1]], start[0], start[1]));
        }
        
        int[,] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (queue.Count > 0) {
            var (x, y) = queue.Dequeue();
            
            for (int i = 0; i < 4; i++) {
                int nx = x + dirs[i, 0];
                int ny = y + dirs[i, 1];
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && 
                    grid[nx][ny] > 0 && dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    queue.Enqueue((nx, ny));
                    
                    if (grid[nx][ny] >= low && grid[nx][ny] <= high) {
                        items.Add((dist[nx][ny], grid[nx][ny], nx, ny));
                    }
                }
            }
        }
        
        items.Sort((a, b) => {
            if (a.distance != b.distance) return a.distance.CompareTo(b.distance);
            if (a.price != b.price) return a.price.CompareTo(b.price);
            if (a.row != b.row) return a.row.CompareTo(b.row);
            return a.col.CompareTo(b.col);
        });
        
        var result = new List<IList<int>>();
        for (int i = 0; i < Math.Min(k, items.Count); i++) {
            result.Add(new List<int> { items[i].row, items[i].col });
        }
        
        return result;
    }
}

var highestRankedKItems = function(grid, pricing, start, k) {
    const m = grid.length;
    const n = grid[0].length;
    const [low, high] = pricing;
    const [startRow, startCol] = start;
    
    const queue = [[startRow, startCol, 0]];
    const visited = new Set();
    visited.add(`${startRow},${startCol}`);
    
    const items = [];
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    while (queue.length > 0) {
        const [row, col, dist] = queue.shift();
        const price = grid[row][col];
        
        if (price >= low && price <= high) {
            items.push([dist, price, row, col]);
        }
        
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            const key = `${newRow},${newCol}`;
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && 
                !visited.has(key) && grid[newRow][newCol] > 0) {
                visited.add(key);
                queue.push([newRow, newCol, dist + 1]);
            }
        }
    }
    
    items.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        if (a[1] !== b[1]) return a[1] - b[1];
        if (a[2] !== b[2]) return a[2] - b[2];
        return a[3] - b[3];
    });
    
    return items.slice(0, k).map(item => [item[2], item[3]]);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	分析
时间复杂度	O(mn + nlog(n))
空间复杂度	O(mn)

时间复杂度：BFS 遍历所有可达单元格需要 O(mn)，排序符合条件的物品最多需要 O(nlog(n))
空间复杂度：距离数组和队列最多需要 O(mn) 的空间

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目