🚀 算法题 🚀 |
🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯
🚀 算法题 🚀 |
🚩 题目链接
- 面试题 17.24. 最大子矩阵
⛲ 题目描述
给定一个正整数、负整数和 0 组成的 N × M 矩阵,编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2],其中 r1, c1 分别代表子矩阵左上角的行号和列号,r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵,返回任意一个均可。
注意:本题相对书上原题稍作改动
示例:
输入:
[
[-1,0],
[0,-1]
]
输出:[0,1,0,1]
解释:输入中标粗的元素即为输出所表示的矩阵
说明:
1 <= matrix.length, matrix[0].length <= 200
🌟 求解思路&实现代码&运行结果
⚡ 动态规划
🥦 求解思路
- 再学习这道题题目之前,大家可以先去看一下另一道最大子数组和的题解,再来学习这道题目就会非常容易。【LeetCode: 53. 最大子数组和 | 暴力递归=>记忆化搜索=>动态规划 | 分治法 】
- 我们先来简单理解一下这道题目的意思,这道题目区别于53.最大子数组和最大的不同在于,53题是一维的,但是这道题目是一个升级的版本,是二维的,但是核心的求解内思路是一样的。
- 既让说思路是一样的?那么我现在知道怎么求解一个一维数组的方法,但是并不知道二维数组怎么求解?这该怎么办呢?我们直接将二维数组转换为一维数组进性求解即可,怎么转换呢?就是挨个遍历从start开始,到end结束的行,按照列对其进行一个压缩即可。
- 然后我们找到最大子矩阵的和,如果当前的子矩阵的和是最大的,我们直接更新,并且抓取矩阵的坐标,最后直接返回即可。
- 有了基本的思路,接下来我们就来通过代码来实现一下。
🥦 实现代码
class Solution {
public int[] getMaxMatrix(int[][] matrix) {
int m=matrix.length,n=matrix[0].length;
int r1=0,c1=0,r2=0,c2=0;
int max=Integer.MIN_VALUE,cur=0;
for(int i=0;i<m;i++){
int[] temp=new int[n];
for(int j=i;j<m;j++){
int start=0;
cur=0;
for(int k=0;k<n;k++){
temp[k]+=matrix[j][k];
cur+=temp[k];
if(cur>max){
max=cur;
r1=i;
c1=start;
r2=j;
c2=k;
}
if(cur<0){
cur=0;
start=k+1;
}
}
}
}
return new int[]{r1,c1,r2,c2};
}
}
🥦 运行结果
时间复杂度:O(M*M*N)
空间复杂度:O(N)
💬 共勉
最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉! |
文章来源:https://www.toymoban.com/news/detail-462331.html
文章来源地址https://www.toymoban.com/news/detail-462331.html
到了这里,关于【LeetCode: 面试题 17.24. 最大子矩阵 | 动态规划 】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!