文档章节

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
博文 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

没有更多内容

加载失败,请刷新页面

加载更多

CentOS7全局安装composer

1. 下载composer-setup.php到当前目录 php -r "copy('https://install.phpcomposer.com/installer', 'composer-setup.php');" 2. 安装 php composer-setup.php 3. 将composer设置成全局 mv c......

月夜中徘徊
9分钟前
1
0
20180920上课截图

小丑鱼00
16分钟前
1
0
基于TCP的远程服务调用

前言 上篇,分析了基于HTTP方式的RPC调用。本篇将在上篇的基础上,分析基于TCP方式的RPC调用。代码的整体思路是一致的,可以看作是在上篇功能上的扩展——即通信的方式。 代码:https://git...

MarvelCode
18分钟前
1
0
67:shell脚本介绍 | shell脚本结构 | 执行data命令用法 | shell脚本中变量

1、shell脚本介绍: shell是一种脚本语言和传统的开发语言相比,会比较简单: shell有自己语法,可以支持逻辑判断、循环等语法: 可以自定义函数,目的是减少重复的代码: shell是系统命令的集合...

芬野de博客
42分钟前
1
0
json schema

json schema是用来验证和描述json对象结构的。 在线验证:https://www.jsonschemavalidator.net/ json schema 编辑器,推荐VSCode,写上"$schema": "https://raw.githubusercontent.com/jso......

谷永权
47分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部