11— 矩阵中移动的最大次数【LeetCode2684】
11— 矩阵中移动的最大次数【LeetCode2684】
吃猫的鱼Code
发布于 2023-07-24 18:32:58
发布于 2023-07-24 18:32:58
题目
2684. 矩阵中移动的最大次数 - 力扣（LeetCode）
给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。
你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：
从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1)和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。
返回你在矩阵中能够 移动 的 最大 次数。
示例一：
img
输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出：3
解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
可以证明这是能够移动的最大次数。示例二：
img
输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
输出：0
解释：从第一列的任一单元格开始都无法移动。解题
解法一
思路
按照题目，能到达的列数，就是最终的答案，因此我们需要用一个result记录当前最大到达的列数（初始值为-1），便于后面返回，同时用一个dp[][]数组记录每个点的可达情况。
建立一个dp[][]数组，用来存储到达每个单元格是否可达，遍历第一列开始。
用两个for循环进行遍历，第一个for循环遍历列，第二个for循环遍历每一行的每个元素，然后进行扫描，不是第一列的情况下，要是遇到dp[i][j]是0的情况直接跳过本次循环（该点不可达）。
然后一直扫描，要是一趟扫描下来result!=i，证明当前已经无法往前移动了，直接返回result+1即可。等所有都遍历完毕，需要看最后一列中dp[][]是否有可达标记，要是有可达标记 result+1，要是没有可达标记，直接返回result
解决
class Solution {
public int maxMoves(int[][] grid) {
//建立dp数组，记录可达情况
int[][] dp = new int[grid.length][grid[0].length];
int result=-1;
for(int i=0;i < grid[0].length-1;i++){ //遍历每一列
for(int j=0;j=0?j-1:j][i+1]>grid[j][i]){ //判断右上那个是否符合
dp[j-1>=0?j-1:j][i+1] = 1;
result = i;
}
if(grid[j][i+1]>grid[j][i]){
dp[j][i+1] = 1;
result = i;
}
if(grid[j+1< grid.length?j+1:j][i+1]>grid[j][i]){
dp[j+1< grid.length?j+1:j][i+1] = 1;
result = i;
}
}
if(result!=i){ //证明当前已经无法往前移动了，直接返回结果即可
return result+1;
}
}
//判断最后一列是否有记录
for(int i=0;i< grid.length;i++){
if(dp[i][grid[0].length-1]==1){
result++;
break;
}
}
return result;
}
}结果
> 2023/07/18 17:41:02
解答成功:
执行耗时:4 ms,击败了93.94% 的Java用户
内存消耗:53.4 MB,击败了76.62% 的Java用户本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。