算法

(dijkstra) $O(nmlog(nm))$

我们可以使用任一单源最短路径的算法（例如Dijkstra算法），只需要在维护当前路径长度时，将其修改为题目中的定义即可。
1. 用堆来保存每次bfs拓展的点，每次需要拓展时因为由堆来维护，所以总是从绝对值最小的开始拓展
2. 当某一点拓展过一次后，即计算过该路径的绝对值最大的最小后，不会再进行拓展，用vis数组进行标记

时间复杂度 $O(nmlog(nm))$

Java 代码

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int n = heights.length;
        int m = heights[0].length;

        PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        q.offer(new int[]{0, 0, 0});
        int[] dist = new int[n * m];
        boolean[] vis = new boolean[n * m];

        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int x = t[0], y = t[1], d = t[2];
            int id = x * m + y;
            if (vis[id]) continue;
            vis[id] = true;
            dist[id] = d;
            for (int i = 0; i < 4; i ++ ) {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < n && b >= 0 && b < m && !vis[a * m + b]) {
                    q.offer(new int[]{a, b, Math.max(d, Math.abs(heights[x][y] - heights[a][b]))});
                }
            }
        }
        return dist[n * m - 1];
    }
}