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

Stella981
• 阅读 629

矩形区域不超过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 }
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
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
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Stella981 Stella981
3年前
Leetcode 424.替换后的最长重复字符
替换后的最长重复字符给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 _k_次。在执行上述操作后,找到包含重复字母的最长子串的长度。注意:字符串长度和_k_不会超过 104。示例1:输入:s"ABAB",k2输
为什么mysql不推荐使用雪花ID作为主键
作者:毛辰飞背景在mysql中设计表的时候,mysql官方推荐不要使用uuid或者不连续不重复的雪花id(long形且唯一),而是推荐连续自增的主键id,官方的推荐是auto_increment,那么为什么不建议采用uuid,使用uuid究
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这