DeepSeek LintCode 258 · 地图跳跃 public int mapJump(int[][] arr)-Seo优化-合肥市网站建设公司

我来为你详细分析 LintCode 258 题「地图跳跃」的解法。

题目理解

题目描述：

给定一个二维数组arr，每个位置有一个高度值
从左上角(0,0)出发，要到达右下角(n-1, m-1)
可以向上、下、左、右四个方向移动
每次跳跃的高度差不能超过k（k 是需要求解的最小值）
求能够到达终点的最小k值

解题思路

这是一个典型的最小值最大化问题，可以用二分答案 + BFS/DFS 验证来解决。

算法思路

二分查找可能的 k 值范围
- 最小可能：0（所有格子高度相同）
- 最大可能：max(arr) - min(arr)（最大高度差）
验证函数：对于给定的 k，判断是否能从起点走到终点
- 使用 BFS 或 DFS 遍历
- 只允许走高度差 ≤ k 的相邻格子

代码实现

解法一：二分查找 + BFS

publicclassSolution{/** * @param arr: the height map * @return: the minimum k */publicintmapJump(int[][]arr){if(arr==null||arr.length==0||arr[0].length==0){return0;}intn=arr.length;intm=arr[0].length;// 找到地图中的最小和最大高度intminHeight=Integer.MAX_VALUE;intmaxHeight=Integer.MIN_VALUE;for(inti=0;i<n;i++){for(intj=0;j<m;j++){minHeight=Math.min(minHeight,arr[i][j]);maxHeight=Math.max(maxHeight,arr[i][j]);}}// 二分查找最小的 kintleft=0;intright=maxHeight-minHeight;while(left+1<right){intmid=left+(right-left)/2;if(canReach(arr,mid)){right=mid;}else{left=mid;}}// 先检查 left，再检查 rightif(canReach(arr,left)){returnleft;}returnright;}// BFS 验证是否能以最大高度差 k 到达终点privatebooleancanReach(int[][]arr,intk){intn=arr.length;intm=arr[0].length;// 四个方向：上、下、左、右int[][]dirs={{-1,0},{1,0},{0,-1},{0,1}};boolean[][]visited=newboolean[n][m];Queue<int[]>queue=newLinkedList<>();// 从起点开始queue.offer(newint[]{0,0});visited[0][0]=true;while(!queue.isEmpty()){int[]curr=queue.poll();intx=curr[0];inty=curr[1];// 到达终点if(x==n-1&&y==m-1){returntrue;}// 尝试四个方向for(int[]dir:dirs){intnx=x+dir[0];intny=y+dir[1];// 检查边界if(nx<0||nx>=n||ny<0||ny>=m){continue;}// 检查是否访问过if(visited[nx][ny]){continue;}// 检查高度差是否在允许范围内intheightDiff=Math.abs(arr[nx][ny]-arr[x][y]);if(heightDiff>k){continue;}visited[nx][ny]=true;queue.offer(newint[]{nx,ny});}}returnfalse;}}

解法二：二分查找 + DFS

publicclassSolution{privateint[][]dirs={{-1,0},{1,0},{0,-1},{0,1}};privateintn,m;privateint[][]arr;publicintmapJump(int[][]arr){if(arr==null||arr.length==0||arr[0].length==0){return0;}this.arr=arr;this.n=arr.length;this.m=arr[0].length;// 找到高度范围intminH=arr[0][0],maxH=arr[0][0];for(inti=0;i<n;i++){for(intj=0;j<m;j++){minH=Math.min(minH,arr[i][j]);maxH=Math.max(maxH,arr[i][j]);}}// 二分查找intleft=0,right=maxH-minH;while(left<right){intmid=left+(right-left)/2;if(canReach(mid)){right=mid;}else{left=mid+1;}}returnleft;}privatebooleancanReach(intk){boolean[][]visited=newboolean[n][m];returndfs(0,0,k,visited);}privatebooleandfs(intx,inty,intk,boolean[][]visited){// 到达终点if(x==n-1&&y==m-1){returntrue;}visited[x][y]=true;// 尝试四个方向for(int[]dir:dirs){intnx=x+dir[0];intny=y+dir[1];if(nx<0||nx>=n||ny<0||ny>=m||visited[nx][ny]){continue;}if(Math.abs(arr[nx][ny]-arr[x][y])<=k){if(dfs(nx,ny,k,visited)){returntrue;}}}returnfalse;}}

解法三：并查集（Union Find）

publicclassSolution{classUnionFind{int[]parent;UnionFind(intn){parent=newint[n];for(inti=0;i<n;i++){parent[i]=i;}}intfind(intx){if(parent[x]!=x){parent[x]=find(parent[x]);}returnparent[x];}voidunion(intx,inty){introotX=find(x);introotY=find(y);if(rootX!=rootY){parent[rootX]=rootY;}}booleanisConnected(intx,inty){returnfind(x)==find(y);}}publicintmapJump(int[][]arr){if(arr==null||arr.length==0||arr[0].length==0){return0;}intn=arr.length;intm=arr[0].length;// 收集所有可能的边（相邻格子）List<int[]>edges=newArrayList<>();int[]dx={0,1};// 只需要向右和向下，避免重复int[]dy={1,0};for(inti=0;i<n;i++){for(intj=0;j<m;j++){for(intd=0;d<2;d++){intni=i+dx[d];intnj=j+dy[d];if(ni<n&&nj<m){intdiff=Math.abs(arr[ni][nj]-arr[i][j]);edges.add(newint[]{i*m+j,ni*m+nj,diff});}}}}// 按高度差排序edges.sort((a,b)->a[2]-b[2]);UnionFinduf=newUnionFind(n*m);intstart=0;intend=n*m-1;// 从小到大尝试连接for(int[]edge:edges){uf.union(edge[0],edge[1]);if(uf.isConnected(start,end)){returnedge[2];}}return0;}}

算法分析

时间复杂度

解法一/二：O(log(maxH) × N × M)
- 二分查找：O(log(maxH))
- 每次验证：O(N × M)
解法三：O(N × M × log(N × M))
- 排序边：O(N × M × log(N × M))

空间复杂度

所有解法：O(N × M) 用于 visited 数组或并查集

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1int[][]arr1={{1,2},{3,4}};System.out.println(solution.mapJump(arr1));// 输出: 1// 测试用例2int[][]arr2={{1,5,3},{2,7,4},{6,8,9}};System.out.println(solution.mapJump(arr2));// 输出: 2// 测试用例3 - 所有格子高度相同int[][]arr3={{1,1},{1,1}};System.out.println(solution.mapJump(arr3));// 输出: 0}