2023.12.11力扣每日一题——最小体力消耗路径_力扣1631

题目来源

力扣每日一题；题序：1631

我的题解

方法一 DFS暴力解法 （无法通过）

在这个题可以直接使用DFS计算起始点到每一个点直接的最小体力消耗，但是计算过程中存在许多重复计算，在时间上过不了。

时间复杂度：应该是 O(m^2*n2)
空间复杂度：主要是递归调用和visited数组占用的空间

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int m=heights.length,n=heights[0].length;
        if(m==1&&n==1)
            return 0;
        boolean[][] visited=new boolean[m][n];
        visited[0][0]=true;
        for(int i=0;i<4;i++){
            int x=pos[i][0];
            int y=pos[i][1];
            if(check(heights,x,y)&&!visited[x][y]){
                visited[x][y]=true;
                dfs(heights,visited,heights[0][0],0,x,y);
                visited[x][y]=false;
            }
        }
        return res;
    }
    int[][] pos={{0,-1},{-1,0},{0,1},{1,0}};
    int res=Integer.MAX_VALUE;
    public void dfs(int[][] heights,boolean[][] visited,int pre,int curMax,int row,int col){
        if(row==heights.length-1&&col==heights[0].length-1){
            curMax=Math.max(curMax,Math.abs(heights[row][col]-pre));
            res=Math.min(res,curMax);
        }
        curMax=Math.max(curMax,Math.abs(heights[row][col]-pre));
        pre=heights[row][col];
        for(int i=0;i<4;i++){
            int x=row+pos[i][0];
            int y=col+pos[i][1];
            if(check(heights,x,y)&&!visited[x][y]){
            	if(curMax>=res)
                    continue;
                visited[x][y]=true;
                dfs(heights,visited,pre,curMax,x,y);
                visited[x][y]=false;
            }
        }
    }
    public boolean check(int[][] heights,int x,int y){
        if(x<0||x>=heights.length||y<0||y>=heights[0].length)
            return false;
        return true;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

方法二 BFS/DFS+二分查找

只要从左上角开始进行深度优先搜索或者广度优先搜索，在搜索的过程中只允许经过边权不超过 x 的边，搜索结束后判断是否能到达右下角即可。
随着 x 的增大，原先可以经过的边仍然会被保留，因此如果当 x=$x_0$时，我们可以从左上角到达右下角，那么当 x>$x_0$时同样也可以可行的。因此我们可以使用二分查找的方法，找出满足要求的最小的那个 x值，记为 $x_{ans}$ ，那么：
当 $x<x_{ans}$ ，我们无法从左上角到达右下角；
当 $x>=x_{ans}$ ，我们可以从左上角到达右下角。
由于格子的高度范围为 [1, $10^6$]，因此我们可以的范围 [0, $10^6$-1]内对 x 进行二分查找。在每一步查找的过程中，我们使用进行深度优先搜索或者广度优先搜索判断是否可以从左上角到达右下角，并根据判定结果更新二分查找的左边界或右边界即可。

时间复杂度：O(mnlogC)，其中 m 和 n 分别是地图的行数和列数，C 是格子的最大高度
空间复杂度：O(mn)，即为广度优先搜索中使用的队列需要的空间

class Solution {
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int minimumEffortPath(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        int left = 0, right = 999999, ans = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            Queue<int[]> queue = new LinkedList<int[]>();
            queue.offer(new int[]{0, 0});
            boolean[] seen = new boolean[m * n];
            seen[0] = true;
            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                int x = cell[0], y = cell[1];
                for (int i = 0; i < 4; ++i) {
                    int nx = x + dirs[i][0];
                    int ny = y + dirs[i][1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && !seen[nx * n + ny] && Math.abs(heights[x][y] - heights[nx][ny]) <= mid) {
                        queue.offer(new int[]{nx, ny});
                        seen[nx * n + ny] = true;
                    }
                }
            }
            if (seen[m * n - 1]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

并查集

最短路径算法

今天感冒了，人不舒服，其他解法后续加上

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈