2146. 价格范围内最高排名的 K 样物品（Rating 1836）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

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

Rating 1836

思路

BFS一下，将所有在pricing范围内的格点按照优先级加入到一个优先队列，并维护优先队列的长度为K

代码

class Solution:
    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
        dir = [-1, 0, 1, 0, -1]
        m, n = len(grid), len(grid[0])
        q = deque()
        q.append((start[0], start[1]))
        vis = set()
        vis.add((start[0], start[1]))
        hpq = []
        dis = 0
        while q: # bfs
            sz = len(q)
            while sz:
                sz -= 1
                x, y = q.popleft()
                if pricing[0] <= grid[x][y] <= pricing[1]: # pricing范围内的格点
                    heapq.heappush(hpq, (-dis, -grid[x][y], -x, -y)) # python默认小顶堆，所以取反加入堆中，这样先pop的是优先级比较低的格点
                    while len(hpq) > k: # 维护长度为k
                        heapq.heappop(hpq)
                for d in range(4):
                    nx = x + dir[d]
                    ny = y + dir[d + 1]
                    if nx < 0 or nx >= m or ny < 0 or ny >= n:
                        continue
                    if grid[nx][ny] == 0:
                        continue
                    if (nx, ny) in vis:
                        continue
                    q.append((nx, ny))
                    vis.add((nx, ny))
            dis += 1
        ret = []
        while hpq:
            _, _, x, y = heapq.heappop(hpq)
            ret.append((-x, -y))
        return ret[::-1] # 从堆中按顺序取出后，取反