说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。
题目描述
给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。
你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：
- 从单元格
(row, col)可以移动到(row - 1, col + 1)、(row, col + 1)和(row + 1, col + 1)三个单元格中任一满足值 严格 大于当前单元格的单元格。
返回你在矩阵中能够 移动 的 最大 次数。
示例 1：
输入： 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).
可以证明这是能够移动的最大次数。
示例 2：
输入： grid = [[3,2,4],[2,1,9],[1,1,7]]
输出： 0
解释： 从第一列的任一单元格开始都无法移动。
提示：
m == grid.lengthn == grid[i].length2 <= m, n <= 10004 <= m * n <= 10^51 <= grid[i][j] <= 10^6
解题思路
- 新建一个二维数组，用于记录每一个位置可以走的最大步数
const rows = grid.length,
cols = grid[0].length;
const dp = new Array(rows).fill(null).map(() => Array(cols).fill(0));
- 根据题目描述进行遍历，题目要求的是要从第一列开始，所以我们一个个要先遍历列再遍历行
for (let j = 0; j < cols - 1; j++) {
for (let i = 0; i < rows; i++) {
...
}
}
- 如果当前遍历的不为第一列且其值为0，则说明不能继续往后走了
if (j > 0 && dp[i][j] == 0) continue;
- 如果当前遍历的不为第一行，那么可以往右上角进行遍历，判断右上角的值是否比其大即可
if (i > 0 && grid[i - 1][j + 1] > grid[i][j]) {
dp[i - 1][j + 1] = Math.max(dp[i][j] + 1, dp[i - 1][j + 1]);
res = Math.max(dp[i - 1][j + 1], res);
}
- 如果当前遍历的不为最后一行，那么可以往右下角进行遍历，判断右下角的值是否比其大即可
if (i < rows - 1 && grid[i + 1][j + 1] > grid[i][j]) {
dp[i + 1][j + 1] = Math.max(dp[i][j] + 1, dp[i + 1][j + 1]);
res = Math.max(dp[i + 1][j + 1], res);
}
- 判断右边的值是否比其大
if (grid[i][j + 1] > grid[i][j]) {
dp[i][j + 1] = Math.max(dp[i][j] + 1, dp[i][j + 1]);
res = Math.max(dp[i][j + 1], res);
}
- 最后返回获取到的最大步数即可
return res;
AC代码
/**
* @param {number[][]} grid
* @return {number}
*/
var maxMoves = function (grid) {
const rows = grid.length,
cols = grid[0].length;
const dp = new Array(rows).fill(null).map(() => Array(cols).fill(0));
let res = 0;
for (let j = 0; j < cols - 1; j++) {
for (let i = 0; i < rows; i++) {
if (j > 0 && dp[i][j] == 0) continue;
if (i > 0 && grid[i - 1][j + 1] > grid[i][j]) {
dp[i - 1][j + 1] = Math.max(dp[i][j] + 1, dp[i - 1][j + 1]);
res = Math.max(dp[i - 1][j + 1], res);
}
if (grid[i][j + 1] > grid[i][j]) {
dp[i][j + 1] = Math.max(dp[i][j] + 1, dp[i][j + 1]);
res = Math.max(dp[i][j + 1], res);
}
if (i < rows - 1 && grid[i + 1][j + 1] > grid[i][j]) {
dp[i + 1][j + 1] = Math.max(dp[i][j] + 1, dp[i + 1][j + 1]);
res = Math.max(dp[i + 1][j + 1], res);
}
}
}
return res;
};
公众号
关注公众号『前端也能这么有趣』，获取更多有趣内容。
说在后面
🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『
前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。
