文档章节

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
05/06
0
0
volley imagerequest

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

lightUp
2016/07/16
3
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
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

没有更多内容

加载失败,请刷新页面

加载更多

&和&&,==和equals的区别

&和&& 相同点:都可以表示逻辑与(and),当运算符两边的结果都为true时,结果才为true,只要有一边为false,结果就为false。 不同点:&&还有短路的作用,即如果第一个表达式的结果为false,就...

森林之下
6分钟前
0
0
我和 Spring 大神的一天

摘要: 先介绍一下故事的5位主人公。 Josh Long 龙之春:Spring 技术布道师,撰写过5部著作,录制过3部畅销的培训视频,是一位开源软件贡献者。 Spencer Gibb:Spring 技术布道师,Spring Cl...

阿里云官方博客
9分钟前
0
0
【Zookeeper】源码分析目录(保存)

https://www.cnblogs.com/leesf456/p/6518040.html

Java搬砖工程师
12分钟前
0
0
vue-cli图片路径使用

https://www.cnblogs.com/minigrasshopper/p/8011630.html

LM_Mike
13分钟前
0
0
前方高能,重要通知!明珠不蒙尘,有才你就来。

11月开源众包服务之星计划--开发商招募正式开启了! 您还是否在为能接更多的订单而操碎了心? 开源众包即将迎来三周年华诞,重磅上线服务之星品牌计划。你有强大的技术实力?你有丰富的案例经...

开源中国众包平台
15分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部