Maximal Rectangle&Largest Rectangle in Histogram

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

首先是Largest Rectangle in Histogram这个题目

 1 class Solution {
 2 public:
 3     int largestRectangleArea(vector<int> &height) {
 4         int len=height.size();
 5         if(len<=0) return 0;
 6         stack<int> s;
 7         int j=0,h,w,maxArea;
 8         while(j<len){
 9             if(s.empty()||height[s.top()]<=height[j]) s.push(j++);//栈空或者有大于栈顶的柱，则一直入栈
10             else {//计算当前范围内的最大矩形面积
11                 h=height[s.top()];//高度
12                 s.pop();
13                 w=s.empty()?j:j-1-s.top();//宽度
14                 maxArea=max(maxArea,w*h);
15             }
16         }
17         while(!s.empty()){//遍历栈中的元素，考虑宽度也占优势原因
18             h=height[s.top()];
19             s.pop();
20             w=s.empty()?len:len-1-s.top();
21             maxArea=max(maxArea,w*h);
22         }
23         return maxArea;
24     }
25 };

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

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
      int row=matrix.size();
      if(row==0) return 0;
      int column=matrix[0].size();
      if(column==0) return 0;

      //计算从当前点开始此行中连续的1的个数
      int ** dpNum=(int**) malloc(sizeof(int *)*row);
      int i,j,k;
      for(i=0;i<row;i++){
        dpNum[i]=(int*)calloc(column,sizeof(int));
        for(j=column-1;j>=0;j--){
          if(matrix[i][j]=='1'){
            if(j==column-1) dpNum[i][j]=1;
            else dpNum[i][j]=1+dpNum[i][j+1];
          } else {
            dpNum[i][j]=0;
          }
        }
      }

      //按照最大矩形面积计算，使用一个栈保存中间子矩阵遍历高度。
      int maxArea=0,height=0,width=INT_MAX,currentArea=INT_MAX;
      for(i=0;i<column;i++){

        j=0;
        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()-1;
            maxArea=max(maxArea,width*height);
          }
        }

        while(!s.empty()){
            width=dpNum[s.top()][i];
            s.pop();
            height=s.empty()?row:row-s.top()-1;
            maxArea=max(maxArea,width*height);
        }
      }

      return maxArea;
    }
};

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