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

题目来自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};

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));
}