文档章节

Maximal Rectangle

曾劲松
 曾劲松
发布于 2016/08/16 22:00
字数 177
阅读 14
收藏 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
博文 200
码字总数 141434
作品 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
2018/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
C++类定义与类构造,重载

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

Echo1
2014/04/03
374
0

没有更多内容

加载失败,请刷新页面

加载更多

iOS个人中心渐变动画、微信对话框、标签选择器、自定义导航栏、短信验证输入框等源码

iOS精选源码 简单的个人中心页面-自定义导航栏并予以渐变动画 程序员取悦女票的正确姿势---Tip1(iOS美容篇) iOS 前台重启应用和清除角标的问题 微信原生提醒对话框3.0 JHLikeButton - 有趣...

Android爱开源
15分钟前
0
0
Yii2使用驼峰命名的形式访问控制器

yii2在使用的时候,访问控制器的时候,如果控制器的名称是驼峰命名法,那访问的url中要改成横线的形式。例如: public function actionRoomUpdate(){//}//访问的时候就要www.test.co...

dragon_tech
18分钟前
0
0
Navicat使用教程:使用Navicat Query Analyzer优化查询性能(第2部分)

下载Navicat Monitor最新版本 Navicat Monitor 是一套安全、简单而且无代理的远程服务器监控工具。它具有强大的功能使你的监控发挥最大效用。受监控的服务器包括 MySQL、MariaDB 和 Percona ...

电池盒
24分钟前
0
0
Python3 读写utf-8文本文件

with open('testRead.txt', 'r', encoding='utf-8') as f: for each_line in f: Passwith open('testWrite.txt', 'w', encoding='utf-8') as f: f.write('写入的内容'......

编程老陆
27分钟前
0
0
Linux syslog相关函数详解

介绍 syslog是Unix系统的日志系统。可以将日志记录在本地系统中。 一个完整的syslong日志包含如下信息:程序模块 | 严重性 | 时间 | 主机名 | 进程名 | 进程ID | 正文。 syslong相关函数 1....

RongJinhui0
31分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部