2024-12-22：矩阵中的最大得分。用go语言，给定一个由正整数构成的 m x n 矩阵 grid，你可以从任意单元格开始，

福大大架构师每日一题

发布于 2024-12-23 14:16:51

5700

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2024-12-22：矩阵中的最大得分。用go语言，给定一个由正整数构成的 m x n 矩阵 grid，你可以从任意单元格开始，移动到正下方或正右侧的任一单元格（不要求相邻）

在从值为 c1 的单元格移动到值为 c2 的单元格时，得分计算为 c2 - c1。

你的目标是至少移动一次，并找到能够获得的最大总得分。

请返回这个最大得分。

m == grid.length。

n == grid[i].length。

2 <= m, n <= 1000。

4 <= m * n <= 100000。

1 <= grid[i][j] <= 100000。

输入：grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]。

输出：9。

解释：从单元格 (0, 1) 开始，并执行以下移动：

1.从单元格 (0, 1) 移动到 (2, 1)，得分为 7 - 5 = 2 。

2.从单元格 (2, 1) 移动到 (2, 2)，得分为 14 - 7 = 7 。

总得分为 2 + 7 = 9 。

答案2024-12-22：

chatgpt[1]

题目来自leetcode3148。

大体步骤如下：

1.创建一个二维数组 premin 用于存储每个单元格的最小值，初始化为 math.MaxInt 值。

2.初始化一个变量 ans 用于记录最大得分，初始值为 math.MinInt。

3.遍历矩阵的每个单元格，对于当前单元格 (i, j)：

• 设定一个变量 pre 用于记录从上方或左方移动过程中的最小值，初始值为 math.MaxInt。
• 如果当前位置不在第一行，则更新 pre 为 min(pre, premin[(i-1)&1][j])。
• 如果当前位置不在第一列，则更新 pre 为 min(pre, premin[i&1][j-1])。
• 如果 i+j > 0，即不在第一行且不在第一列，则更新 ans 为 max(ans, grid[i][j] - pre)。
• 将当前位置的值更新为 min(pre, grid[i][j])。

4.返回最终的最大得分 ans。

总的时间复杂度：

• 外层循环遍历行，内层循环遍历列，时间复杂度为 O(m*n)。

总的额外空间复杂度：

• 除了输入矩阵外，主要额外使用了 premin 二维数组和几个变量，它们占用的空间与输入矩阵大小相关。
• premin 占用的空间是 O(n)，其他额外空间占用是 O(1)。

综上所述，总的时间复杂度为 O(m*n)，总的额外空间复杂度为 O(n)。

Go完整代码如下：

package main

import(
"fmt"
"math"
)

func maxScore(grid [][]int)int{
    m, n :=len(grid),len(grid[0])
    premin :=make([][]int,2)
for i :=range premin {
        premin[i]=make([]int, n)
for j :=range premin[i]{
            premin[i][j]= math.MaxInt
}
}
    ans := math.MinInt
for i :=0; i < m; i++{
for j :=0; j < n; j++{
            pre := math.MaxInt
if i >0{
                pre = min(pre, premin[(i -1)&1][j])
}
if j >0{
                pre = min(pre, premin[i &1][j -1])
}
// i = j = 0 时没有转移
if i + j >0{
                ans = max(ans, grid[i][j]- pre)
}
            premin[i&1][j]= min(pre, grid[i][j])
}
}
return ans
}

func main(){
    grid :=[][]int{{9,5,7,3},{8,9,6,1},{6,7,14,3},{2,5,3,1}}
    fmt.Println(maxScore(grid))
}

Rust完整代码如下：

use std::cmp::{min, max};

fnmax_score(grid:&Vec<Vec<i32>>)->i32{
letm= grid.len();
letn= grid[0].len();
letmut premin=vec![vec![i32::MAX; n];2];
letmut ans= i32::MIN;

foriin0..m {
forjin0..n {
letmut pre= i32::MAX;
if i >0{
                pre =min(pre, premin[(i -1)&1][j]);
}
if j >0{
                pre =min(pre, premin[i &1][j -1]);
}
if i + j >0{
                ans =max(ans, grid[i][j]- pre);
}
            premin[i &1][j]=min(pre, grid[i][j]);
}
}

    ans
}

fnmain(){
letgrid=vec![
vec![9,5,7,3],
vec![8,9,6,1],
vec![6,7,14,3],
vec![2,5,3,1]
];

println!("{}",max_score(&grid));
}