提示

deque 是 Python 标准库 collections 模块中的一个类，它代表了双端队列（Double-Ended Queue）。 deque 允许从队列的两端进行高效的插入和删除操作，因此它在许多需要频繁操作两端元素的场景中比 list 更加高效。

主要特点： 双端队列：可以在队列的两端进行插入和删除操作，支持高效的 append 、 appendleft 、 pop 、 popleft 等方法。

时间复杂度：

append(x) 和 appendleft(x) ：在队列两端插入元素，时间复杂度为 O(1)。

pop() 和 popleft() ：从队列两端删除元素，时间复杂度为 O(1)。

访问队列中间的元素时，时间复杂度为 O(n)。

如果是本地编辑器编写代码，记得导入：

from collections import deque

1. 1926. 迷宫中离入口最近的出口

   思路：开辟一个双端队列 q = deque() ，先把起点加进去，然后开始 while q 循环，把这一轮 q 内的节点加进去，遍历节点的上下左右，如果遇到边界就 return ，遇到空地就加入 q ，并把当前空地改为墙。

   class Solution:
   def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
       m, n = len(maze), len(maze[0])
       q = deque()
       q.append(entrance) # 加入起点
       maze[entrance[0]][entrance[1]] = "+" # 起点视为墙
       step = 0
       while q:
           step += 1
           for _ in range(len(q)):
               i, j = q.popleft()
               for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                   if 0 <= x < m and 0 <= y < n and maze[x][y] == ".":
                       if x in (0, m - 1) or y in (0, n - 1):
                           return step
                       q.append([x, y])
                       maze[x][y] = "+"
       return -1

   时间复杂度：O(mn)，其中 m 和 n 分别为 maze 的行数和列数。

   空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。

2. 1091. 二进制矩阵中的最短路径

   提示

   八方向的可以使用语句：

   for x in range(i - 1, i + 2):
       for y in range(j - 1, j + 2):

   class Solution:
   def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
       if grid[0][0] == 1:
           return -1
       n = len(grid)
       if n == 1:
           return 1
       q = deque()
       q.append((0, 0))
       step = 1
       while q:
           step += 1
           for _ in range(len(q)):
               i, j = q.popleft()
               temp = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
               for r, c in temp:
                   x = i + r
                   y = j + c
                   if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:
                       if (x, y) == (n - 1, n - 1):
                           return step
                       q.append((x, y))
                       grid[x][y] = 1
       return -1

   时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

   空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。

3. 1162. 地图分析

   曼哈顿距离就是只能横着和竖着走；这题是多源 bfs ，先把所有陆地加入队列，每一轮循环，所有陆地都往上下左右走一步，合法的路加入队列，最终走到最后的就是最远的距离

   class Solution:
   def maxDistance(self, grid: List[List[int]]) -> int:
       m, n = len(grid), len(grid[0])
       q = deque()
       for i in range(m):
           for j in range(n):
               if grid[i][j]:
                   q.append((i, j))
       step = -1
       if len(q) == m * n:
           return -1
       while q:
           step += 1
           for _ in range(len(q)):
               i, j = q.popleft()
               for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                   if 0 <= x < m and 0 <= y < n and grid[x][y] == 0:
                       q.append((x, y))
                       grid[x][y] = 1
       return step

   时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

   空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。

4. 542. 01 矩阵

   也是多源 bfs ，注意将 0 视为源

   class Solution:
   def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
       m, n =len(mat), len(mat[0])
       res = [[0] * n for _ in range(m)]
       from collections import deque
       q = deque()
       for i in range(m):
           for j in range(n):
               if mat[i][j] == 0:
                   q.append((i, j))
       step = 0
       while q:
           step += 1
           for _ in range(len(q)):
               i, j = q.popleft()
               for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                   if 0 <= x < m and 0 <= y < n and mat[x][y] == 1:
                       res[x][y] = step
                       q.append((x, y))
                       mat[x][y] = 6
       return res

   时间复杂度：O(mn)，其中 m 和 n 分别为 mat 的行数和列数。

   空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。

5. 994. 腐烂的橘子

   也是多源 bfs ，将烂橘子视为源，注意要剩余新鲜橘子才进循环

   class Solution:
   def orangesRotting(self, grid: List[List[int]]) -> int:
       m, n = len(grid), len(grid[0])
       q = deque()
       fresh = 0
       for i in range(m):
           for j in range(n):
               if grid[i][j] == 2:
                   q.append((i, j))
               elif grid[i][j] == 1:
                   fresh += 1
       step = 0
       while q and fresh:
           step += 1
           for _ in range(len(q)):
               i, j = q.popleft()
               for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                   if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
                       q.append((x, y))
                       fresh -= 1
                       grid[x][y] = 2
       return -1 if fresh else step

   时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

   空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。

6. 1765. 地图中的最高点

   也是多源 bfs ，将海洋视为源，从队列中取出节点，每轮向上下左右走，合法的赋予高度，直到遍历完整个矩阵

   class Solution:
   def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
       m, n = len(isWater), len(isWater[0])
       height = [[0] * n for _ in range(m)]
       visited = isWater
       q = deque()
       for i in range(m):
           for j in range(n):
               if isWater[i][j]:
                   q.append((i, j))
       step = 0
       while q:
           step += 1
           for _ in range(len(q)):
               i, j = q.popleft()
               for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                   if 0 <= x < m and 0 <= y < n and not visited[x][y]:
                       height[x][y] = step
                       q.append((x, y))
                       visited[x][y] = 1
       return height

   时间复杂度：O(mn)，其中 m 和 n 分别为 isWater 的行数和列数。

   空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。

7. 934. 最短的桥

   求两岛之间的最短路径，把其中一个岛所在的点视为源（可以通过 dfs 做到），转化成求多源 bfs 的最短路径，只要有源走到了另一个岛即可结束，此时就是最短路径

   class Solution:
   def shortestBridge(self, grid: List[List[int]]) -> int:
       m, n = len(grid), len(grid[0])
       def dfs(i, j):
           if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != 1:
               return
           grid[i][j] = 2
           q.append((i, j))
           dfs(i - 1, j)
           dfs(i + 1, j)
           dfs(i, j - 1)
           dfs(i, j + 1)
   
       i, j = next((i, j) for i in range(m) for j in range(n) if grid[i][j]) # 通过迭代器找到第一个岛的一个点
       q = deque()
       dfs(i, j) # 从这点 dfs 这个岛，并在遍历过程中把岛中的点加入 q
       step = -1
       while q:
           step += 1
           for _ in range(len(q)):
               i, j = q.popleft()
               for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                   if 0 <= x < m and 0 <= y < n:
                       if grid[x][y] == 1: # 走到另一个岛了
                           return step
                       elif grid[x][y] == 0: # 走到海洋了
                           q.append((x, y))
                           grid[x][y] = 2 # 标记来过了

   时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

   空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。

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

   这题很有意思，因为距离是最优先，故本题可以视为单源 bfs，向外走的时候把空地（grid[i][j]为1）和物品坐标（grid[i][j]大于1）加入列表 q ，排序 q （按照价值，行坐标，列坐标三个优先级的顺序），把合法价格（low <= grid[i][j] <= high）的坐标加入到结果 res 中，如果 len(res) 大于等于 k 了，说明物品足够了，返回前 k 个坐标，即 res[:k] ，如果不够继续遍历 q ，直到足够 k 个

   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])
       q = [(start[0], start[1])]
       res = []
       visited = {(start[0], start[1])}
       low, high = pricing
       while q: # p 是一个坐标，包含横坐标和纵坐标
           q.sort(key=lambda p: (grid[p[0]][p[1]], p))
           res.extend(p for p in q if low <= grid[p[0]][p[1]] <= high)
           if len(res) >= k:
               return res[:k]
           temp = q
           q = []
           for i, j in temp:
               for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                   if 0 <= x < m and 0 <= y < n and grid[x][y] and (x, y) not in visited:
                       q.append([x, y])
                       visited.add((x, y))
       return res

   时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

   空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。