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.
题意有一个01组成的矩阵，找到其中面积最大的，全部由1构成的子矩阵。
去年做多校比赛的时候第一次见到这题，不优化到O（n×n）死活过不了当时。
优化就是先预处理成保存成，当前点向上都是1的最高的高度，就变成每一行都是一个直方图，
之后用O（n）的直方图求最大面积去算，之前一篇文章 http://blog.csdn.net/havenoidea/article/details/11854723介绍过这个步骤，就不细说。
int height[1000][1000];class Solution {public: int maximalRectangle(vector<vector<char> > &matrix) { int i,j,k,row,col,maxx=0; row=matrix.size(); if(row==0)return 0; col=matrix[0].size(); if(col==0)return 0; for(j=0;j<col;++j) for(i=0;i<row;++i) if(matrix[i][j]=='0')height[i][j]=0; else if(i==0)height[0][j]=1; else height[i][j]=height[i-1][j]+1; stack<int>s; for(i=0;i<row;++i) { for(j=0;j<col;++j) { if(s.empty())s.push(j); else { while(!s.empty()&&height[i][s.top()]>height[i][j]) { int ph=s.top(); s.pop(); if(!s.empty()) maxx=max(maxx,(j-s.top()-1)*height[i][ph]); else maxx=max(maxx,j*height[i][ph]); } s.push(j); } } while(!s.empty()) { int ph=s.top(); s.pop(); if(!s.empty()) maxx=max(maxx,(col-s.top()-1)*height[i][ph]); else maxx=max(maxx,col*height[i][ph]); } } return maxx; }};