Medium

题目描述

给你一个 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^5
  • 1 <= grid[i][j] <= 10^5

提示：

  • 从单元格 (x1, y1) 到另一个单元格 (x2, y2) 的任何路径的得分总是 grid[x2][y2] - grid[x1][y1]。
  • 假设我们固定起始单元格 (x1, y1)，如何找到单元格 (x2, y2) 使得值 grid[x2][y2] - grid[x1][y1] 尽可能最大？

解题思路

这道题的核心洞察是：任何从位置 (x1, y1) 到位置 (x2, y2) 的路径得分都等于 grid[x2][y2] - grid[x1][y1]，与具体路径无关。

基于这个观察，问题转化为：找到两个位置 (i1, j1) 和 (i2, j2)，使得 i1 ≤ i2 且 j1 ≤ j2（保证能从前者到达后者），并且 grid[i2][j2] - grid[i1][j1] 最大。

解法一：暴力枚举 枚举所有可能的起点和终点对，时间复杂度 O(m²n²)，对于大规模数据会超时。

解法二：动态规划（推荐） 我们可以用动态规划优化。定义 dp[i][j] 为以位置 (i, j) 作为终点能获得的最大得分。

关键思路：对于位置 (i, j)，它可以从其左上方的任意位置到达。我们需要在所有可能的起点中找到能使得分最大的那个。

为了避免重复计算，我们维护一个 minVal[i][j]，表示位置 (i, j) 左上方区域（包括 (i, j)）的最小值。这样，以 (i, j) 为终点的最大得分就是 grid[i][j] - minVal[i][j]（前提是这个得分大于 0）。

状态转移：

  • minVal[i][j] = min(grid[i][j], minVal[i-1][j], minVal[i][j-1])
  • dp[i][j] = max(dp[i-1][j], dp[i][j-1], grid[i][j] - minVal[i-1][j], grid[i][j] - minVal[i][j-1])

这样我们就能在 O(mn) 时间内解决问题。

代码实现

class Solution {
public:
    int maxScore(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> minVal(m, vector<int>(n));
        
        minVal[0][0] = grid[0][0];
        for (int j = 1; j < n; j++) {
            minVal[0][j] = min(minVal[0][j-1], grid[0][j]);
        }
        for (int i = 1; i < m; i++) {
            minVal[i][0] = min(minVal[i-1][0], grid[i][0]);
        }
        
        int maxScore = INT_MIN;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0) {
                    maxScore = max(maxScore, grid[i][j] - minVal[i-1][j]);
                    minVal[i][j] = min(minVal[i-1][j], grid[i][j]);
                }
                if (j > 0) {
                    maxScore = max(maxScore, grid[i][j] - minVal[i][j-1]);
                    minVal[i][j] = min(minVal[i][j], minVal[i][j-1]);
                }
            }
        }
        
        return maxScore;
    }
};

class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        min_val = [[0] * n for _ in range(m)]
        
        min_val[0][0] = grid[0][0]
        for j in range(1, n):
            min_val[0][j] = min(min_val[0][j-1], grid[0][j])
        for i in range(1, m):
            min_val[i][0] = min(min_val[i-1][0], grid[i][0])
        
        max_score = float('-inf')
        
        for i in range(m):
            for j in range(n):
                if i > 0:
                    max_score = max(max_score, grid[i][j] - min_val[i-1][j])
                    min_val[i][j] = min(min_val[i-1][j], grid[i][j])
                if j > 0:
                    max_score = max(max_score, grid[i][j] - min_val[i][j-1])
                    min_val[i][j] = min(min_val[i][j], min_val[i][j-1])
        
        return max_score

public class Solution {
    public int MaxScore(IList<IList<int>> grid) {
        int m = grid.Count, n = grid[0].Count;
        int[,] minVal = new int[m, n];
        
        minVal[0, 0] = grid[0][0];
        for (int j = 1; j < n; j++) {
            minVal[0, j] = Math.Min(minVal[0, j-1], grid[0][j]);
        }
        for (int i = 1; i < m; i++) {
            minVal[i, 0] = Math.Min(minVal[i-1, 0], grid[i][0]);
        }
        
        int maxScore = int.MinValue;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0) {
                    maxScore = Math.Max(maxScore, grid[i][j] - minVal[i-1, j]);
                    minVal[i, j] = Math.Min(minVal[i-1, j], grid[i][j]);
                }
                if (j > 0) {
                    maxScore = Math.Max(maxScore, grid[i][j] - minVal[i, j-1]);
                    minVal[i, j] = Math.Min(minVal[i, j], minVal[i, j-1]);
                }
            }
        }
        
        return maxScore;
    }
}

var maxScore = function(grid) {
    const m = grid.length, n = grid[0].length;
    const minVal = Array(m).fill().map(() => Array(n).fill(0));
    
    minVal[0][0] = grid[0][0];
    for (let j = 1; j < n; j++) {
        minVal[0][j] = Math.min(minVal[0][j-1], grid[0][j]);
    }
    for (let i = 1; i < m; i++) {
        minVal[i][0] = Math.min(minVal[i-1][0], grid[i][0]);
    }
    
    let maxScore = -Infinity;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i > 0) {
                maxScore = Math.max(maxScore, grid[i][j] - minVal[i-1][j]);
                minVal[i][j] = Math.min(minVal[i-1][j], grid[i][j]);
            }
            if (j > 0) {
                maxScore = Math.max(maxScore, grid[i][j] - minVal[i][j-1]);
                minVal[i][j] = Math.min(minVal[i][j], minVal[i][j-1]);
            }
        }
    }
    
    return maxScore;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度动态规划解法
时间复杂度O(mn)
空间复杂度O(mn)

其中 m 为矩阵的行数，n 为矩阵的列数。空间复杂度可以通过滚动数组优化到 O(n)。

相关题目