正文

Maximal Rectangle&Largest Rectangle in Histogram

IP云
IP云V管理员/5 阅读
11/30
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

这两天在做leetcode的题目，最大矩形的题目以前遇到很多次了，一直都是用最笨的方法，扫描每个柱子，变换宽度，计算矩形面积，一直都以为就这样O(n 2 )的方法了，没有想到居然还有研究出了O(n)的算法，真是对GeeksForGeeks大神膜拜啊。

首先是Largest Rectangle in Histogram这个题目 

 class Solution {

 public:

     int largestRectangleArea(vector<int> &height) {

         int len=height.size();

         if(len<=) return ;

         stack<int> s;

         int j=,h,w,maxArea;

         while(j<len){

             if(s.empty()||height[s.top()]<=height[j]) s.push(j++);//栈空或者有大于栈顶的柱，则一直入栈

             else {//计算当前范围内的最大矩形面积

                 h=height[s.top()];//高度

                 s.pop();

                 w=s.empty()?j:j--s.top();//宽度

                 maxArea=max(maxArea,w*h);

             }

         }

         while(!s.empty()){//遍历栈中的元素，考虑宽度也占优势原因

             h=height[s.top()];

             s.pop();

             w=s.empty()?len:len--s.top();

             maxArea=max(maxArea,w*h);

         }

         return maxArea;

     }

 };

然后是Maximal Rectangle这个题目，考虑到整个矩阵的情况，我们可以把他当成是二维的Largest Rectangle in Histogram，代码如下： 

class Solution {

public:

    int maximalRectangle(vector<vector<char> > &matrix) {

      int row=matrix.size();

      if(row==) return ;

      int column=matrix[].size();

      if(column==) return ;

      //计算从当前点开始此行中连续的1的个数

      int ** dpNum=(int**) malloc(sizeof(int *)*row);

      int i,j,k;

      for(i=;i<row;i++){

        dpNum[i]=(int*)calloc(column,sizeof(int));

        for(j=column-;j>=;j--){

          if(matrix[i][j]==''){

            if(j==column-) dpNum[i][j]=;

            else dpNum[i][j]=+dpNum[i][j+];

          } else {

            dpNum[i][j]=;

          }

        }

      }

      //按照最大矩形面积计算，使用一个栈保存中间子矩阵遍历高度。

      int maxArea=,height=,width=INT_MAX,currentArea=INT_MAX;

      for(i=;i<column;i++){

        j=;

        stack<int> s;

        while(j<row){

          if(s.empty()||dpNum[j][i]>=dpNum[s.top()][i]) s.push(j++);

          else {

            width=dpNum[s.top()][i];

            s.pop();

            height=s.empty()?dpNum[j][i]:dpNum[j][i]-s.top()-;

            maxArea=max(maxArea,width*height);

          }

        }

        while(!s.empty()){

            width=dpNum[s.top()][i];

            s.pop();

            height=s.empty()?row:row-s.top()-;

            maxArea=max(maxArea,width*height);

        }

      }

      return maxArea;

    }

};

我能说开始的时候我只想到了扫描扫描扫描，很少能考虑到是否有更加高效的方法，真是汗颜啊……

Maximal Rectangle&Largest Rectangle in Histogram的更多相关文章
  1. LeetCode之“动态规划”：Maximal Square && Largest Rectangle in Histogram && Maximal Rectangle

    1. Maximal Square 题目链接 题目要求: Given a 2D binary matrix filled with 0's and 1's, find the largest squa ...

  2. 47. Largest Rectangle in Histogram && Maximal Rectangle

    Largest Rectangle in Histogram Given n non-negative integers representing the histogram's bar height ...

  3. 84. Largest Rectangle in Histogram *HARD* -- 柱状图求最大面积 85. Maximal Rectangle *HARD* -- 求01矩阵中的最大矩形

    1. Given n non-negative integers representing the histogram's bar height where the width of each bar ...

  4. [LeetCode] Largest Rectangle in Histogram O(n) 解法详析， Maximal Rectangle

    Largest Rectangle in Histogram Given n non-negative integers representing the histogram's bar height ...

  5. LeetCode 84--柱状图中最大的矩形（ Largest Rectangle in Histogram） 85--最大矩形（Maximal Rectangle）

    84题和85五题 基本是一样的,先说84题 84--柱状图中最大的矩形( Largest Rectangle in Histogram) 思路很简单,通过循环,分别判断第 i 个柱子能够延展的长度le ...

  6. [LeetCode] Largest Rectangle in Histogram 直方图中最大的矩形

    Given n non-negative integers representing the histogram's bar height where the width of each bar is ...

  7. 84. Largest Rectangle in Histogram

    https://www.cnblogs.com/grandyang/p/4322653.html 1.存储一个单调递增的栈 2.如果你不加一个0进去,[1]这种情况就会输出结果0,而不是1 3.单调递 ...

  8. [LeetCode] 84. Largest Rectangle in Histogram 直方图中最大的矩形

    Given n non-negative integers representing the histogram's bar height where the width of each bar is ...

  9. poj 2559 Largest Rectangle in a Histogram - 单调栈

    Largest Rectangle in a Histogram Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 19782 ...

随机推荐
  1. 巧妙使用CSS媒体查询(Media Queries)和JavaScript判断浏览器设备类型的好方法

    有无数的理由要求我们在任何时候都应该知道用户是使用的什么设备浏览我们的网站——宽屏,普通屏,平板,手机?知道这些特征,我们web应用的CSS和JavaScript才能同步做相应的操作.在给Mozill ...

  2. Python网络爬虫（1）--url访问及参数设置

    环境:Python2.7.9 / Sublime Text 2 / Chrome 1.url访问,直接调用urllib库函数即可 import urllib2 url='http://www.baid ...

  3. php单例模式 （转

    假设我们需要写一个类用来操作数据库,并同时满足以下要求: ①SqlHelper类只能有一个实例(不能多)②SqlHelper类必须能够自行创建这个实例③必须自行向整个系统提供这个实例,换句话说:多个对 ...

  4. 面试问题总结二（技术能力-PHP）----Ⅳ

    57.Linux 的基本命令(重点,现在多数服务器都是Linux 系统) 答:arch 显示机器的处理器架构 uname -m 显示机器的处理器架构 uname -r 显示正在使用的内核版本 dmid ...

  5. CSS实现点击改变元素背景色

    可通过使用css伪类实现点击元素变色的效果,两个伪类是:active, :focus :active :active选择器用于选择活动链接.当在一个链接上点击时,它就会成为活动的(激活的),:acti ...

  6. Eclipse HTML Editor

    需插件: 1.GEF 3.1 安装程序下载 下载地址: http://download.eclipse.org/tools/gef/downloads/drops/R-3.1-200507071758 ...

  7. struts2针对mvc的框架 spring针对解耦与事务的框架

    struts2针对mvc的框架 spring针对解耦与事务的框架

  8. BZOJ3439 Kpm的MC密码（可持久化trie）

    将串反过来就变成查询前缀了.考虑建一棵可持久化trie,查询时二分答案,均摊一下复杂度即为O(mlogn). #include<iostream> #include<cstdio&g ...

  9. k序列和

    二分答案是参数搜索的一个改善.是这样,对于一个问题,如果它的答案具有单调性质(即如果i不可行,那么大于i的解都不可行,而小于i的解有可能可行),进而用二分的方法枚举答案,再判断答案是否可行,直到求到符 ...

  10. 深入理解JAVA虚拟机JVM

    深入理解JAVA虚拟机JVM Java 虚拟机(Java virtual machine,JVM)是运行 Java 程序必不可少的机制.java之所以能实现一次编写到处执行,也就是因为jVM.原理:编 ...

相关阅读

目录[+]