设计一个算法解决“热力图”问题，即给定一个二维网格，每个格子有温度值，要求找到从起点到终点的最短路径（温度和最小），请说明算法思路、时间复杂度和空间复杂度。
答案
1) 【一句话结论】：对于给定二维网格的热力图，求起点到终点的最小温度和路径，由于温度值非负（假设），可采用 Dijkstra 算法，通过贪心策略逐步扩展最短路径候选，最终得到最小温度和的路径。
2) 【原理/概念讲解】：Dijkstra 算法适用于带非负权重的图的最短路径问题。核心思想是“贪心选择”：每次从已确定最短路径的节点集合中，选择距离起点最近的未访问节点，然后更新其所有邻居节点的距离。类比：就像找从家到公司的最便宜路线，每次选当前最便宜的车站，然后更新去往其他车站的更便宜路线，直到到达公司。关键步骤包括：初始化起点距离为0，其他为无穷大；维护一个优先队列（最小堆）存储待访问节点及当前距离；每次弹出最小距离节点，若该节点是终点则结束；否则，遍历其所有邻居，计算通过当前节点到达邻居的距离，若更小则更新邻居的距离并加入优先队列。
3) 【对比与适用场景】：对比 Dijkstra 与广度优先搜索（BFS）
| 特性 | Dijkstra 算法 | 广度优先搜索（BFS） |
|---|---|---|
| 适用场景 | 带非负权重的图（如热力图，温度和为非负） | 无权图（每条边权重为1） |
| 算法逻辑 | 贪心选择，优先队列 | 层次遍历，队列 |
| 时间复杂度 | O(E log V)（E为边数，V为顶点数） | O(V + E) |
| 空间复杂度 | O(V) | O(V) |
| 注意点 | 需要非负权重 | 无负权边限制 |
4) 【示例】：假设网格为：
[[1, 3, 1],
[1, 5, 1],
[4, 2, 1]]
起点 (0,0)，终点 (2,2)。温度值表示移动到该格子的温度成本。用 Dijkstra 算法步骤：
- 初始化距离数组
dist，起点dist[0][0]=0，其他为无穷大。 - 优先队列初始为
(0, (0,0))。 - 弹出
(0, (0,0))，更新邻居(0,1)和(1,0)，dist[0][1]=3，dist[1][0]=1，加入队列。 - 弹出
(1, (1,0))，更新邻居(1,1)，dist[1][1]=2（1+1），加入队列。 - 弹出
(2, (1,1))，更新邻居(1,2)和(2,1)，dist[1][2]=3，dist[2][1]=3，加入队列。 - 弹出
(3, (2,1))，更新邻居(2,2)，dist[2][2]=4（2+2），加入队列。 - 弹出
(4, (2,2))，终点，路径为(0,0)→(1,0)→(1,1)→(2,1)→(2,2)，总温度和为 1+1+5+2+1=10（正确）。
伪代码：
def dijkstra(grid, start, end):
n, m = len(grid), len(grid[0])
dist = [[float('inf')] * m for _ in range(n)]
dist[start[0]][start[1]] = 0
pq = [(0, start)]
visited = set()
while pq:
d, u = heapq.heappop(pq)
if u in visited: continue
visited.add(u)
if u == end: return d
for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:
nx, ny = u[0]+dx, u[1]+dy
if 0 <= nx < n and 0 <= ny < m:
nd = d + grid[nx][ny]
if nd < dist[nx][ny]:
dist[nx][ny] = nd
heapq.heappush(pq, (nd, (nx, ny)))
return dist[end[0]][end[1]]
5) 【面试口播版答案】：面试官您好，这个问题求的是热力图上起点到终点的最小温度和路径，由于温度值通常非负，我考虑用 Dijkstra 算法。核心思路是贪心选择：每次从已确定最短路径的节点中，选距离起点最近的未访问节点，更新其邻居的距离。具体来说，初始化起点距离为0，其他为无穷大，用优先队列（最小堆）存储待处理节点。每次弹出最小距离节点，若为终点则结束；否则遍历其所有邻居，计算通过当前节点到达邻居的路径和，若更小则更新并加入队列。这样能保证最终得到的终点距离是最小温度和。时间复杂度是 O(E log V)，空间复杂度 O(V)，其中 E 是边数，V 是节点数。比如对于给定的网格，算法会逐步扩展最短路径候选，最终找到温度和最小的路径。
6) 【追问清单】：
- 问：如果温度值有负数怎么办？
答：如果存在负权边，Dijkstra 不适用，此时应考虑 Bellman-Ford 算法，但需要检查负权环。 - 问：如何优化空间复杂度？
答：可以用二维数组记录距离，优先队列只存储未访问节点，或用数组标记已访问节点，减少存储。 - 问：具体实现中如何处理边界条件？
答：检查起点或终点是否越界，初始化距离数组时设置无穷大，避免未初始化的值影响计算。 - 问：如果网格很大，优先队列的插入和弹出操作如何优化？
答：保持优先队列的有序性，每次操作时间复杂度 O(log V)，总复杂度仍为 O(E log V)，可通过空间换时间（如使用数组模拟堆）优化常数因子。
7) 【常见坑/雷区】：
- 坑1：误用 BFS，因为 BFS 只适用于无权图（每步成本相同），而热力图温度和不同，会导致错误结果。
- 坑2：忽略温度和的累加，错误地只考虑步数，而未计算路径上所有格子的温度值。
- 坑3：复杂度分析错误，比如认为 Dijkstra 是 O(V²)，而实际是 O(E log V)，因为优先队列的优化。
- 坑4：未处理起点到终点不可达的情况，应检查终点是否被访问过，若未访问则返回无穷大。
- 坑5：邻居遍历错误，比如只考虑上下左右，而忽略对角线（若题目允许移动方向），导致路径不完整。