Leetcode 363.矩形区域不超过k的最大数值和

Stella981
• 阅读 329

矩形区域不超过k的最大数值和

给定一个非空二维矩阵 matrix 和一个整数 _k_,找到这个矩阵内部不大于 k 的最大矩形和。

示例:

输入: matrix = [[1,0,1],[0,-2,3]], k = 2

输出: 2

解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2,且 2 是不超过 k 的最大数字(k = 2)。

说明:

  1. 矩阵内的矩形区域面积必须大于 0。
  2. 如果行数远大于列数,你将如何解答呢?

解题思路:

根据题意,寻找二维数组中所有可以组成的矩形中面积不超过k的最大值,所以必须要求出可能组成的矩形的面积并与k比较求出最终结果。这里为了最终不超时,可以在一下方面进行优化:

1.设置一个数组比较当前列(或者行)下已经扫描过的数的和。

2.设置一个TreeMap,保存当前矩阵长度下,已经扫描过得矩形的面积。同时,TreeMap中有快速查找元素的方法,可以快速查找所找的元素。

 1 import java.util.TreeSet;
 2 
 3 public class Solution {
 4     public static int maxSumSubmatrix(int[][] matrix, int target) {
 5         int row = matrix.length;
 6         if(row==0)
 7             return 0;
 8         int col = matrix[0].length;
 9         if(col==0)
10             return 0;
11         int result = Integer.MIN_VALUE;
12         boolean key= col>row?false:true;
13         int m = Math.min(row,col);
14         int n = Math.max(row,col);
15         //一行一行的找
16         for(int i=0;i<m;i++){
17             //找从第i行开始一直到第0行这i+1行的可能组成的矩形长度
18             int[] array = new int[n];//这个矩阵为了保存每一列上第j行到第i行的和
19             for(int j=i;j>=0;j--){
20                 TreeSet<Integer> set = new TreeSet<Integer>();//用来保存当前高度下,长度为从0开始到k位置的矩形的结果。理解set的含义是解决此题的关键。
21                 set.add(0);
22                 int sum=0;
23                 for(int k=0;k<n;k++){
24                     if(key){
25                         array[k]+=matrix[k][j];
26                     }
27                     else{
28                         array[k]+=matrix[j][k];
29                     }
30                     sum+=array[k];
31                     /* 因为要满足  (sum-set中的元素)<=target,
32                      * 而且sum-set中的元素的值要尽可能的大,
33                      * 所以也就是再求小于等于sum-target中满足条件的元素的最小的一个
34                      * 正好TreeSet中提供了这个方法ceil(),可以很方便的找出这个元素
35                      */
36                     Integer integer = set.ceiling(sum-target);
37                     if(integer!=null){
38                         result=Math.max(result, sum-integer);
39                     }
40                     set.add(sum);
41                 }
42             }
43         }
44         return result;
45     }
46 }
点赞
收藏
评论区
推荐文章
光头强的博客 光头强的博客
4个月前
Java面向对象试题
1、请创建一个Animal动物类,要求有方法eat()方法,方法输出一条语句“吃东西”。创建一个接口A,接口里有一个抽象方法fly()。创建一个Bird类继承Animal类并实现接口A里的方法输出一条有语句“鸟儿飞翔”,重写eat()方法输出一条语句“鸟儿吃虫”。在Test类中向上转型创建b对象,调用eat方法。然后向下转型调用eat()方
刚刚好 刚刚好
4个月前
css问题
1、在IOS中图片不显示(给图片加了圆角或者img没有父级)<div<imgsrc""/</divdiv{width:20px;height:20px;borderradius:20px;overflow:h
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
晴空闲云 晴空闲云
4个月前
css中box-sizing解放盒子实际宽高计算
我们知道传统的盒子模型,如果增加内边距padding和边框border,那么会撑大整个盒子,造成盒子的宽度不好计算,在实务中特别不方便。boxsizing可以设置盒模型的方式,可以很好的设置固定宽高的盒模型。盒子宽高计算假如我们设置如下盒子:宽度和高度均为200px,那么这会这个盒子实际的宽高就都是200px。但是当我们设置这个盒子的边框和内间距的时候,那
艾木酱 艾木酱
3个月前
快速入门|使用MemFire Cloud构建React Native应用程序
MemFireCloud是一款提供云数据库,用户可以创建云数据库,并对数据库进行管理,还可以对数据库进行备份操作。它还提供后端即服务,用户可以在1分钟内新建一个应用,使用自动生成的API和SDK,访问云数据库、对象存储、用户认证与授权等功能,可专
Stella981 Stella981
1年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Wesley13 Wesley13
1年前
Java日期时间API系列36
  十二时辰,古代劳动人民把一昼夜划分成十二个时段,每一个时段叫一个时辰。二十四小时和十二时辰对照表:时辰时间24时制子时深夜11:00凌晨01:0023:0001:00丑时上午01:00上午03:0001:0003:00寅时上午03:00上午0
Wesley13 Wesley13
1年前
MySQL查询按照指定规则排序
1.按照指定(单个)字段排序selectfromtable_nameorderiddesc;2.按照指定(多个)字段排序selectfromtable_nameorderiddesc,statusdesc;3.按照指定字段和规则排序selec
Wesley13 Wesley13
1年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
helloworld_28799839 helloworld_28799839
4个月前
常用知识整理
Javascript判断对象是否为空jsObject.keys(myObject).length0经常使用的三元运算我们经常遇到处理表格列状态字段如status的时候可以用到vue
helloworld_34035044 helloworld_34035044
6个月前
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为