哪些网站是用wordpress,傻瓜式做网站哪个软件好,wordpress 增加按钮,数码网站建设论文【LetMeFly】3148.矩阵中的最大得分#xff1a;每个元素与其左或上元素之差的最大值#xff08;原地修改O(1)空间#xff09;
力扣题目链接#xff1a;https://leetcode.cn/problems/maximum-difference-score-in-a-grid/
给你一个由 正整数 组成、大小为 m x n 的矩阵 g…【LetMeFly】3148.矩阵中的最大得分每个元素与其左或上元素之差的最大值原地修改O(1)空间
力扣题目链接https://leetcode.cn/problems/maximum-difference-score-in-a-grid/
给你一个由 正整数 组成、大小为 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.lengthn grid[i].length2 m, n 10004 m * n 1051 grid[i][j] 105
解题方法动态规划
从a移动到b再从b移动到c等价于直接从a移动到c。
因此要求的就是对所有的a到c中c-a的最大值。
怎么求很简单在遍历原始数组的时候将每个值修改为这个元素、这个元素左上方(包含)所有元素的最小值。
这样对应下标为(i, j)的元素其左上方的最小值就是min(grid[i - 1][j], grid[i][j - 1])。
使用grid[i][j]减去这个“最小值”即为从任意一点移动到(i, j)所得的最大得分只能往右或下移动。
所有的最大得分中最大的那个即为所求。
时间复杂度 O ( s i z e ( g r i d ) ) O(size(grid)) O(size(grid))空间复杂度 O ( 1 ) O(1) O(1)可以直接修改grid数组的话空间复杂度就是O(1)
AC代码
C
class Solution {
public:int maxScore(vectorvectorint grid) {int ans grid[0][1] - grid[0][0];for (int i 0; i grid.size(); i) {for (int j 0; j grid[0].size(); j) {int original grid[i][j];if (i 0) {grid[i][j] min(grid[i][j], grid[i - 1][j]);ans max(ans, original - grid[i - 1][j]);}if (j 0) {grid[i][j] min(grid[i][j], grid[i][j - 1]);ans max(ans, original - grid[i][j - 1]);}}}return ans;}
};执行用时分布119ms击败99.11%消耗内存分布55.80MB击败87.46%。
Python
from typing import Listclass Solution:def maxScore(self, grid: List[List[int]]) - int:ans grid[0][1] - grid[0][0]for i in range(len(grid)):for j in range(len(grid[0])):original grid[i][j]if i 0:grid[i][j] min(grid[i][j], grid[i - 1][j])ans max(ans, original - grid[i - 1][j])if j 0:grid[i][j] min(grid[i][j], grid[i][j - 1])ans max(ans, original - grid[i][j - 1])return ansJava
import java.util.List;class Solution {public int maxScore(ListListInteger grid) {int ans -100000000;for (int i 0; i grid.size(); i) {for (int j 0; j grid.get(0).size(); j) {int original grid.get(i).get(j);if (i 0) {grid.get(i).set(j, Math.min(grid.get(i).get(j), grid.get(i - 1).get(j)));ans Math.max(ans, original - grid.get(i - 1).get(j));}if (j 0) {grid.get(i).set(j, Math.min(grid.get(i).get(j), grid.get(i).get(j - 1)));ans Math.max(ans, original - grid.get(i).get(j - 1));}}}return ans;}
}Go
package mainfunc min(a int, b int) int {if a b {return a}return b
}func max(a int, b int) int {if a b {return a}return b
}func maxScore(grid [][]int) int {ans : -12345678for i, line : range grid {for j, item : range line {original : itemif i 0 {grid[i][j] min(grid[i][j], grid[i - 1][j]) // 这里修改item的值不会改变grid[i][j]的值ans max(ans, original - grid[i - 1][j])}if j 0 {grid[i][j] min(grid[i][j], grid[i][j - 1])ans max(ans, original - grid[i][j - 1])}}}return ans
}End
44CC44Gt44GZ44Gn44Kr44OQ44Gr5b2T5pysCg 同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/141234633
