题目描述:
Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.
解题思路:
根据题意,寻找二维数组中所有可以组成的矩形中面积不超过k的最大值,所以必须要求出可能组成的矩形的面积并与k比较求出最终结果。这里为了最终不超时,可以在一下方面进行优化:
1.设置一个数组比较当前列(或者行)下已经扫描过的数的和。
2.设置一个TreeMap,保存当前矩阵长度下,已经扫描过得矩形的面积。同时,TreeMap中有快速查找元素的方法,可以快速查找所找的元素。
具体代码:
public class Solution {
public static int maxSumSubmatrix(int[][] matrix, int target) {
int row = matrix.length;
if(row==0)
return 0;
int col = matrix[0].length;
if(col==0)
return 0;
int result = Integer.MIN_VALUE;
boolean key= col>row?false:true;
int m = Math.min(row,col);
int n = Math.max(row,col);
//一行一行的找
for(int i=0;i<m;i++){
//找从第i行开始一直到第0行这i+1行的可能组成的矩形长度
int[] array = new int[n];//这个矩阵为了保存每一列上第j行到第i行的和
for(int j=i;j>=0;j--){
TreeSet<Integer> set = new TreeSet<Integer>();//用来保存当前高度下,长度为从0开始到k位置的矩形的结果。理解set的含义是解决此题的关键。
set.add(0);
int sum=0;
for(int k=0;k<n;k++){
if(key){
array[k]+=matrix[k][j];
}
else{
array[k]+=matrix[j][k];
}
sum+=array[k];
/* 因为要满足 (sum-set中的元素)<=target,
* 而且sum-set中的元素的值要尽可能的大,
* 所以也就是再求小于等于sum-target中满足条件的元素的最小的一个
* 正好TreeSet中提供了这个方法ceil(),可以很方便的找出这个元素
*/
Integer integer = set.ceiling(sum-target);
if(integer!=null){
result=Math.max(result, sum-integer);
}
set.add(sum);
} }
}
return result;
}
}
【leetcode】363. Max Sum of Rectangle No Larger Than K的更多相关文章
-
【LeetCode】363. Max Sum of Rectangle No Larger Than K 解题报告(Python)
作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 题目地址: https://leetcode.com/problems/max-sum- ...
-
363. Max Sum of Rectangle No Larger Than K
/* * 363. Max Sum of Rectangle No Larger Than K * 2016-7-15 by Mingyang */ public int maxSumSubmatri ...
-
[LeetCode] 363. Max Sum of Rectangle No Larger Than K 最大矩阵和不超过K
Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix s ...
-
363 Max Sum of Rectangle No Larger Than K 最大矩阵和不超过K
Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix s ...
-
第十三周 Leetcode 363. Max Sum of Rectangle No Larger Than K(HARD)
Leetcode363 思路: 一种naive的算法就是枚举每个矩形块, 时间复杂度为O((mn)^2), 可以做少许优化时间复杂度可以降低到O(mnnlogm), 其中m为行数, n为列数. 先求出 ...
-
[LeetCode] Max Sum of Rectangle No Larger Than K 最大矩阵和不超过K
Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix s ...
-
Leetcode: Max Sum of Rectangle No Larger Than K
Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix s ...
-
[Swift]LeetCode363. 矩形区域不超过 K 的最大数值和 | Max Sum of Rectangle No Larger Than K
Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix s ...
-
Max Sum of Rectangle No Larger Than K
Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix s ...
随机推荐
-
Data对象
var myDate = new Date(); Date()返回当日的日期 例如今天是2016/8/19 getFullYear()返回当前日期的年 myDate.getFullYear() 201 ...
-
codeforces#271 (Div. 2)预处理
B. Worms time limit per test 1 second memory limit per test 256 megabytes input standard input outpu ...
-
Java数组扩容算法及Java对它的应用
1)Java数组对象的大小是固定不变的,数组对象是不可扩容的.利用数组复制方法可以变通的实现数组扩容.System.arraycopy()可以复制数组.Arrays.copyOf()可以简便的创建数组 ...
-
从简单需求到OLAP的RANK系列函数
同事问了一个非常简单的问题,怎么取出每个partition里面另外一个列的最小值? create table t1 (int c1, int c2); 假如按照c2分区,0-10,10-20,20 ...
-
Arduino 封装库
这里是一个在Arduino平台下将常用的代码以库的形式封装的示例. 第一步:在Arduino的安装目录下的对应目录建立文件夹 C:\Program Files (x86)\Arduino\librar ...
-
Ubuntu 卸载 VMware
sudo vmware-installer --uninstall-product vmware-workstationsudo vmware-installer --uninstall-produc ...
-
<;转>;十分钟学会javascript
本文转自国外知名网站Learn X in Y minutes. 由于格式的限制无法直接将Markdown转贴过来,所以只能用Iframe的方式. 本文适合有一定编程基础又对Javascript感兴趣的 ...
-
webpy + nginx + fastcgi 构建python应用
1.准备环境 CentOs 6.3 nginx-1.4.2.tar.gz http://nginx.org/download/nginx-1.4.2.tar.gz openss ...
-
Jsp指令有那些?
<%@page language="java" contentType="text/html;charset=gb2312" session=" ...
-
【XSS】对抗蠕虫 —— 如何让按钮不被 JS 自动点击
前言 XSS 自动点按钮有什么危害? 在社交网络里,很多操作都是通过点击按钮发起的,例如发表留言.假如留言系统有 XSS,用户中招后除了基本攻击外,还能进行传播 -- XSS 自动填入留言内容,并模拟 ...