文档章节

Maximal Rectangle

曾劲松
 曾劲松
发布于 2016/08/16 22:00
字数 177
阅读 13
收藏 0
点赞 0
评论 0

对于点A,H[1] = 4, L[1] = 1, R[1] = 2。对应的矩形面积H * (R - L) = 4。

对于点B,H[2] = 3, L[2] = 1, R[2] = 4。对应的矩形面积H * (R - L) = 9。

int maximalRectangle(vector<vector<char> > &matrix){
          if(matrix.size() == 0 || matrix[0].size() == 0)
          return 0;
        
          int m = matrix.size(), n = matrix[0].size(), res = 0;
          vector<int> left(n, 0), right(n, n), height(n, 0);
        
          for(int i = 0; i < m; ++ i){
              int cur_left = 0, cur_right = n;
            
              for(int j = 0; j < n; ++ j) {
                 height[j] = matrix[i][j] == '1' ? height[j] + 1 : 0;
                 left[j] = matrix[i][j] == '1' ? max(left[j], cur_left) : 0;
                 cur_left = matrix[i][j] == '1' ? cur_left : j + 1;
              }
             
              for(int j = n - 1; j >= 0; -- j){
                 right[j] = matrix[i][j] == '1' ? min(right[j], cur_right) : n;
                cur_right = matrix[i][j] == '1' ? cur_right : j;
              }
            
              for(int j = 0; j < n; ++ j)
                 res = max(res, (right[j] - left[j]) * height[j]);
              }
        
          return res;
     }

 

© 著作权归作者所有

共有 人打赏支持
曾劲松
粉丝 4
博文 198
码字总数 141022
作品 0
武汉
2018 TCO Algorithm-Round 1B 600-points题解报告

一、题目 Problem Statement Consider the set of integers between 1 and n, inclusive, and two positive integers c and k. You want to build an ordered list of k pairs (x1, y1), (x2......

海天一树X
05/06
0
0
关于超过mount次数的alert

Solution: When mounting /path/to/device, a warning is seen "kernel: EXT3-fs warning: maximal mount count reached, running e2fsck is recommended". This is a non-fatal warning. Pl......

UVN2015
2017/10/09
0
0
volley imagerequest

通过get 方法获取 image byte data; parse: ->

lightUp
2016/07/16
3
0
sqoop2增量导入无法指定last value问题解决方法

在用sqoop 1.99.6创建任务进行增量导入时,在incremental read后需要输入check column和last value,但是再输入last value时输入任何值都会提示超出了size,size为-1。以下是这个问题的解决方...

林远图raymond
2016/03/14
108
0
[poj1155] TELE 树形DP 01背包

TELE Description A TV-network plans to broadcast an important football match. Their network of transmitters and users can be represented as a tree. The root of the tree is a tra......

myjs999
2017/09/21
0
0
skalibs 1.0.3 发布,低级的 C 程序库

skalibs 1.0.3 发布,更新如下: This release fixes a portability problem on systems that define NSIG as one more than the maximal signal number. skalibs 是一组用于一般用途的、低级......

小卒过河
2011/07/11
236
0
定义一个扁平的按钮样式

<Window.Resources> <Style x:Key="myBtnStyle" TargetType="{x:Type Button}"> <Setter Property="Template"> <Setter.Value> <ControlTemplate TargetType="{x:Type Button}"> <Grid> <Gri......

kaixinguo314
02/08
0
0
C++类定义与类构造,重载

设计一个矩形类,left、top、right、bottom用来指定矩形的4个顶点坐标,由5个成员函数来赋值(见类定义部分),另有显示函数和加减运算。重点为:(1)加减复合赋值语义定义为对矩形的左上角...

Echo1
2014/04/03
355
0
Pku2750 Potted Flower

Description The little cat takes over the management of a new park. There is a large circular statue in the center of the park, surrounded by N pots of flowers. Each potted flow......

qq_39399999
2017/12/24
0
0
c语言实现面向对象编程

介简: Redy的开发语言是C,但在源码中,有很多地方都使用到了面向对象编程的方法,例如:在基本数据类型这一个模块,所有的数据类型都继承robject;在抽象语法树模块,所有的节点都继承ast...

有些服务器
2015/12/06
74
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

mybaitis 通过Mapping 实现多表查询

1.实体类 1.1 用于做多表查询的类 public class CustomerCard { private Integer id;//主键 private String cardNumber; private Integer customerId;//用户id private String customerName;......

kuchawyz
8分钟前
0
0
Java语言学习(八):集合类框架

Java中提供了各种数据集合类,这些类主要用于保存复杂结构的数据。下面将介绍常用的几种集合类的用法。 ArrayList集合可以看做一个动态的数组,比普通数组更加灵活,更适合保存未知数量的数据...

海岸线的曙光
10分钟前
0
0
SpringBoot下Redis相关配置是如何被初始化的

参考网页 SpringBoot集成Redis的原理 https://blog.csdn.net/hry2015/article/details/74276423 https://blog.csdn.net/hry2015/article/details/75451705 application.yml配置文件中的属性是......

karma123
10分钟前
1
0
数据库事务的四大特性以及事务的隔离级别

本篇讲述数据库中事务的四大特性(ACID),并且将会详细地说明事务的隔离级别。 如果一个数据库声称支持事务的操作,那么该数据库必须要具备以下四个特性: ⑴ 原子性(Atomicity) 原子性是...

Java大蜗牛
18分钟前
0
0
Spring Boot 整合 MyBatis/通用Mapper/PageHelper分页插件

整合MyBatis 整合通用Mapper 1. POM依赖配置 <properties><mapper.starter.version>2.0.3-beta1</mapper.starter.version></properties><!-- 通用Mapper --><dependency><groupId>t......

OSC_fly
26分钟前
0
0
CentOS7 双网卡绑定

环境 操作系统 CentOS7.5,禁用 NetworkManager 服务 网卡 eth0 网卡 eth1 绑定网卡 bond0 网卡 eth0 配置 修改 /etc/sysconfig/network-scripts/ifcfg-eth0 TYPE=EthernetBOOTPROTO=noneD......

Colben
28分钟前
0
0
zk实战--rpc框架集群化

在看此篇内容时需要浏览下面内容 netty实战--手写rpc框架 前文功能简介以及功能扩充 利用netty来实现一个点对点的rpc调用。客户端和服务端都是靠手写地址进行socket同学的,无法1对多,也无法...

xpbob
44分钟前
12
0
springboot 发送邮件

获取授权码 添加配置 # 账号和密码spring.mail.username=aaa@qq.comspring.mail.password=bbb# 服务器地址spring.mail.host=smtp.qq.comspring.mail.properties.mail.smtp.ssl.en...

阿豪boy
45分钟前
0
0
如何使用GNU Ring?

文章名:如何使用GNU Ring? 作者:冰焰火灵X 1079092922@qq.com 文章许可:CC BY-SA 4.0 ##1. 安装 下载GNU Ring 点击左边选择你的系统版本(这里以 GNU/Linux 为例,我使用的是Mint 18.3)...

ICE冰焰火灵X
48分钟前
4
0
深入理解springMVC

什么是spring MVC Spring MVC属于SpringFrameWork的后续产品,已经融合在Spring Web Flow里面。Spring 框架提供了构建 Web 应用程序的全功能 MVC 模块。使用 Spring 可插入的 MVC 架构,从而...

Java填坑之路
53分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部