3148：矩阵中的最大得分（1819 分）

2024-05-12 约 424 字预计阅读 1 分钟次阅读

力扣第 397 场周赛第 3 题

题目

给你一个由 正整数 组成、大小为 m x n 的矩阵 grid。你可以从矩阵中的任一单元格移动到另一个位于正下方或正右侧的任意单元格（不必相邻）。从值为 c1 的单元格移动到值为 c2 的单元格的得分为 c2 - c1 。

你可以从任一单元格开始，并且必须至少移动一次。

返回你能得到的最大总得分。

示例 1：

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

输出：9

解释：从单元格 (0, 1) 开始，并执行以下移动：
- 从单元格 (0, 1) 移动到 (2, 1)，得分为 7 - 5 = 2 。
- 从单元格 (2, 1) 移动到 (2, 2)，得分为 14 - 7 = 7 。
总得分为 2 + 7 = 9 。

示例 2：

输入：grid = [[4,3,2],[3,2,1]]

输出：-1

解释：从单元格 (0, 0) 开始，执行一次移动：从 (0, 0) 到 (0, 1) 。得分为 3 - 4 = -1 。

提示：

m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 10⁵
1 <= grid[i][j] <= 10⁵

相似问题：

3225：网格图操作后的最大分数

分析

等价于求最大的两数之差，遍历每个位置，维护其左上的最小值，作差即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        m,n = len(grid),len(grid[0])
        res = -inf
        for i,j in product(range(m),range(n)):
            a = grid[i-1][j] if i else inf
            b = grid[i][j-1] if j else inf
            res = max(res,grid[i][j]-min(a,b))
            grid[i][j] = min(grid[i][j],a,b)
        return res

356 ms

目录

3148：矩阵中的最大得分（1819 分）

题目

分析

解答