找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1523|回复: 1
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Maximal Rectangle】-【刷题第一弹2014】

[复制链接]

18

主题

11

精华

478

积分

高级会员

Rank: 3Rank: 3

积分
478
发表于 10-15-2014 06:08 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
Maximal Rectangle
Leetcode 传送门

题目:
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.


汇总传送门


相关题目:
[Largest Rectangle in Histogram]

本帖被以下淘专辑推荐:

18

主题

11

精华

478

积分

高级会员

Rank: 3Rank: 3

积分
478
 楼主| 发表于 10-15-2014 06:17 PM | 显示全部楼层
本帖最后由 wyu277 于 10-15-2014 06:19 PM 编辑

思路:
首先,你如果对Largest Rectangle in Histogram理解的够深的话,
这题就没什么难度。每行都是一个Largest Rectangle in Histogram的题。

你需要一个array,
对于当前行,你只需要累计每列到当前行的矩柱的高度。
也就是累计1的个数。
然后,就当一个Largest Rectangle in Histogram来做。
keep track 最大值。

这题的解法, 我很早就在leetcode 讨论区发过一个帖子。
Leetcode 讨论帖
上code:
  1. public int maximalRectangle(char[][] matrix) {
  2.     if (matrix == null || matrix.length==0)
  3.         return 0;
  4.    
  5.     int[] h = new int[matrix[0].length+1];
  6.     int max = 0;
  7.    
  8.     for (int i=0;i<matrix.length;i++)
  9.     {
  10.         Stack<Integer> index = new Stack<>();
  11.         for (int j=0;j<h.length;j++)
  12.         {
  13.             h[j] = (j<h.length-1&&matrix[i][j]=='1')?h[j]+1 : 0;
  14.             if (index.isEmpty()||h[j]>=h[index.peek()])
  15.             {
  16.                 index.push(j);
  17.             }
  18.             else
  19.             {
  20.                 while (!index.isEmpty()&&h[j]<h[index.peek()]) {
  21.                     int height = h[index.pop()];
  22.                     int area = height * (index.isEmpty()? j: j-index.peek()-1);
  23.                     max = Math.max(max,area);
  24.                 }
  25.                 index.push(j);
  26.             }
  27.         }
  28.     }
  29.    
  30.     return max;
  31. }
复制代码

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表