Java实现 LeetCode 363 矩形区域不超过 K 的最大数值和
2023-09-14 08:58:05 时间
363. 矩形区域不超过 K 的最大数值和
给定一个非空二维矩阵 matrix 和一个整数 k,找到这个矩阵内部不大于 k 的最大矩形和。
示例:
输入: matrix = [[1,0,1],[0,-2,3]], k = 2
输出: 2
解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2,且 2 是不超过 k 的最大数字(k = 2)。
说明:
矩阵内的矩形区域面积必须大于 0。
如果行数远大于列数,你将如何解答呢?
class Solution {
public static int maxSumSubmatrix(int[][] matrix, int k) {
int m = matrix.length;
int n = matrix[0].length;
int[][] sums = new int[m][n];
/**
* 按照列来求和
*/
for(int col = 0 ; col < n; col ++){
for(int row = 0 ; row < m ; row ++){
if(row == 0)
sums[row][col] = matrix[row][col];
else
sums[row][col] = sums[row - 1][col] + matrix[row][col];
}
}
/**
* col1为矩阵起始列,col2为矩阵结尾列
*/
int result = Integer.MIN_VALUE ;
for(int col1 = 0 ; col1 < n ; col1 ++){
for(int col2 = col1; col2 < n ; col2++){
/**
* set中都是存放的是startCol和endCol相同的矩阵的和
*/
TreeSet<Integer> set = new TreeSet<>();
set.add(0);
for(int row = 0 ; row < m ; row++){
int sum = 0; //子矩阵的和
for(int i = col1; i <= col2 ; i ++){
sum += sums[row][i];
}
//求出set中大于等于(sum - k)最小值
if(set.ceiling(sum - k) != null){
int max = sum - set.ceiling(sum - k);
result = result > max ? result : max;
}
set.add(sum);
}
}
}
return result;
}
}
相关文章
- java random函数原理_详解JAVA中Random()函数的用法
- java locale 中国_Java描述语言、国家和地理的类——Locale
- java中map根据value找key_Java Map和Map<String, Object>类型,map通过value找key
- Java多态理解_什么是java多态
- rtsp 获取视频流 java_Java获取rtsp视频流,实现rtsp流预览功能,并将视频流每帧保存成图片…
- java在线播放_Java实现视频在线播放flv视频
- java解释器虚拟机-Java代码如何运行在Java虚拟机中
- 实现Java程序操作MySQL数据库(java调用mysql)
- Java连接MySQL:实现数据互通(java如何连接mysql)
- Java 连接 MySQL 数据库简易实现(java连mysql)
- 标题:Linux下发布Java:开创新纪元(linux发布java)
- Linux调用Java实现编程快速开发(linux调用java)
- Java轻松使用Redis实现数据高效存储(java使用redis)
- Java连接SQL Server:实现数据库完美对接(java链接sqlserver)
- MySQL与Java的结合:实现强大的数据持久化功能(mysql与java)
- Java轻松处理Redis缓存(java处理redis)
- 使用Java连接MySQL数据库的具体操作方法(java连接mysql代码)
- Java程序调用Linux系统命令实现更多功能(java调用linux命令)
- 使用Java语言写Redis实现一个分布式缓存系统(用java写个redis)
- Java迭代Oracle实现数据库更高性能(java迭代oracle)
- 编程玩转Java之Oracle编程实战(java中的oracle)
- Java使用Oracle实现优雅数据查询(java.oracle)
- 利用Redis锁实现Java程序并发控制(redis锁java实现)