【Leetcode】1631. Path With Minimum Effort
题目地址:
https://leetcode.com/problems/path-with-minimum-effort/
给定一个
m
m
m行
n
n
n列二维矩阵,要从左上角
(
0
,
0
)
(0,0)
(0,0)位置走到右下角
(
m
−
1
,
n
−
1
)
(m-1,n-1)
(m−1,n−1)位置,每一步可以走上下左右四个方向(当然不能走出界),使得该路径的所有相邻点的数值差的绝对值的最大值最小。返回这个最小值。为了方便理解,这里举个例子:
对于上面的图,绿色所显示的路径中,所有相邻节点的差的绝对值中最大的是
∣
5
−
3
∣
|5-3|
∣5−3∣等于
2
2
2,并且任意别的路径,都无法取到更小的差。
法1:最小生成树。我们可以将整个矩阵看成一个带权无向图,每个坐标看成一个点,两个坐标的数值差看成是边权,这样问题就变为,所有从左上到右下的路径中,最大边权最小的路径的那个最小边权是多少。思路和证明参考https://blog.****.net/qq_46105170/article/details/108481056,大致是这样做的:
用最小生成树的Kruskal算法。先将边按照权值排序,然后一条一条地将边加上去,一旦发现左上角和右下角连通了之后,正在加的那条边的权值就是答案(判断连通需要用到并查集)。
代码如下:
class Solution {
public:
struct Edge {
int x, y, w;
};
vector<int> p;
int minimumEffortPath(vector<vector<int>>& hs) {
int m = hs.size(), n = hs[0].size(), mn = m * n;
p.resize(mn);
for (int i = 0; i < mn; i++) p[i] = i;
vector<Edge> v;
auto f = [&](int x, int y) { return x * n + y; };
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (i + 1 < m)
v.push_back({f(i + 1, j), f(i, j), abs(hs[i + 1][j] - hs[i][j])});
if (j + 1 < n)
v.push_back({f(i, j + 1), f(i, j), abs(hs[i][j + 1] - hs[i][j])});
}
sort(v.begin(), v.end(), [&](auto& e1, auto& e2) { return e1.w < e2.w; });
auto merge = [&](int x, int y) {
int px = find(p[x]), py = find(y);
if (px == py) return;
p[px] = py;
};
for (int i = 0; i < v.size(); i++) {
int x = v[i].x, y = v[i].y, w = v[i].w;
merge(x, y);
if (find(f(0, 0)) == find(f(m - 1, n - 1))) return w;
}
return 0;
}
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
};
时间复杂度 O ( m n log ( m n ) ) O(mn\log (mn)) O(mnlog(mn))(排序的时间),空间 O ( m n ) O(mn) O(mn)。
法2:修改版Dijkstra。Dijkstra算法求的是非负权无向图的最短路问题,而这题相当于是将一条路的长度定义为其所有边边权的最大值,接下来模仿Dijkstra算法的方法用最小堆来做即可。算法正确性证明和Dijkstra算法求最短路类似,只需注意,当一条路径增加一条边的时候,其最大边权不会变的更小。代码如下:
import java.util.Arrays;
import java.util.PriorityQueue;
public class Solution {
// 这个类里的x和y是坐标,maxDiff指的是到这个坐标的路径的最大边权
class Pair {
int x, y, maxDiff;
public Pair(int x, int y, int maxDiff) {
this.x = x;
this.y = y;
this.maxDiff = maxDiff;
}
}
public int minimumEffortPath(int[][] heights) {
// 特判一些显然的情况
if (heights == null || heights.length == 0 || heights[0].length == 0) {
return 0;
}
int m = heights.length, n = heights[0].length;
if (m == 1 && n == 1) {
return 0;
}
// 按到达pair的路径的最大边权来排优先级,最大边权小者优先
PriorityQueue<Pair> minHeap = new PriorityQueue<>((p1, p2) -> Integer.compare(p1.maxDiff, p2.maxDiff));
boolean[][] visited = new boolean[m][n];
// 记录到每个位置的所有路径中最大边权最小的那个路径的最大边权
int[][] minMaxdiff = new int[m][n];
// 初始化为正无穷
for (int i = 0; i < minMaxdiff.length; i++) {
Arrays.fill(minMaxdiff[i], Integer.MAX_VALUE);
}
int[] dir = {1, 0, -1, 0, 1};
minHeap.offer(new Pair(0, 0, 0));
minMaxdiff[0][0] = 0;
while (!minHeap.isEmpty()) {
Pair cur = minHeap.poll();
int x = cur.x, y = cur.y;
if (x == m - 1 && y == n - 1) {
return minMaxdiff[m - 1][n - 1];
}
// 标记一下已求出
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nextX = x + dir[i], nextY = y + dir[i + 1];
if (inBound(nextX, nextY, m, n) && !visited[nextX][nextY]) {
int curDiff = Math.abs(heights[nextX][nextY] - heights[x][y]);
int maxDiff = Math.max(curDiff, cur.maxDiff);
if (minMaxdiff[nextX][nextY] > maxDiff) {
minMaxdiff[nextX][nextY] = maxDiff;
minHeap.offer(new Pair(nextX, nextY, maxDiff));
}
}
}
}
return -1;
}
private boolean inBound(int x, int y, int m, int n) {
return 0 <= x && x < m && 0 <= y && y < n;
}
}
时间复杂度 O ( m n log ( m n ) ) O(mn\log (mn)) O(mnlog(mn))(入堆出堆的时间需要 O ( log ( m n ) ) O(\log (mn)) O(log(mn))),空间 O ( m n ) O(mn) O(mn)。
上一篇: tencent cloud