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 mainimport ( "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};fn max_score(grid: &Vec<Vec<i32>>) -> i32 { let m = grid.len(); let n = grid[0].len(); let mut premin = vec![vec![i32::MAX; n]; 2]; let mut ans = i32::MIN; for i in 0..m { for j in 0..n { let mut 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}fn main() { let grid = 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));}

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP