1.枚举法（超时）
public class Solution {
public int largestRectangleArea(int[] height) {
int max=-1;
for(int i=0;i<height.length;i++)
{
int len=1;
int k=i-1;
while(k>=0&&height[k]<=height[i])
{
k--;
len++;
}
k=i+1;
while(k<height.length&&height[k]<=height[i])
{
len++;
k++;
}
if(max<len)
{
max=len;
}
}
return max;
}
}
2.单调栈(AC)，其实模拟了第一种方法，nyoj做过，效率为线性。写的代码有点长，但是很好理解
class node
{
int d; //di
int h;// higtht
} public class Solution {
public int largestRectangleArea(int[] height) {
int len=height.length;
if(len==0) return 0;
node n[]=new node[len];
for(int i=0;i<len;i++)
{
n[i]=new node();
n[i].d=1;
n[i].h=height[i]; }
Stack<node> s=new Stack<node>();
s.push(n[0]);
int max=n[0].h;
for(int j=1;j<len;j++)
{
node t=s.peek();
if(n[j].h>=t.h)
{
s.push(n[j]);
}
else
{
int with=0;
while(!s.isEmpty()&&s.peek().h>n[j].h)
{
t=s.pop();
with+=t.d;
if(with*t.h>max) max=with*t.h; }
n[j].d+=with;
s.push(n[j]); } }
int with=0;
while(!s.isEmpty())
{
node t=s.pop();
with=with+t.d;
int temp=t.h*with; if(temp>max) max=temp; } return max;
}}
3.最大01矩阵()。使用上述四项，枚举每一行。
class node
{
int d; //di
int h;// higtht
} public class Solution {
public int largest(int[] height) {
int len=height.length;
if(len==0) return 0;
node n[]=new node[len];
for(int i=0;i<len;i++)
{
n[i]=new node();
n[i].d=1;
n[i].h=height[i]; }
Stack<node> s=new Stack<node>();
s.push(n[0]);
int max=n[0].h;
for(int j=1;j<len;j++)
{
node t=s.peek();
if(n[j].h>=t.h)
{
s.push(n[j]);
}
else
{
int with=0;
while(!s.isEmpty()&&s.peek().h>n[j].h)
{
t=s.pop();
with+=t.d;
if(with*t.h>max) max=with*t.h; }
n[j].d+=with;
s.push(n[j]); } }
int with=0;
while(!s.isEmpty())
{
node t=s.pop();
with=with+t.d;
int temp=t.h*with; if(temp>max) max=temp; } return max;
}
public int maximalRectangle(char[][] matrix) {
if(matrix.length==0) return 0; int len=matrix[0].length;
int ans[]=new int[len];
for(int i=0;i<len;i++)
{
ans[i]=matrix[0][i]-'0';
}
int max=largest(ans); for(int i=1;i<matrix.length;i++)
{
for(int j=0;j<matrix[0].length;j++)
{
if(matrix[i][j]=='0') ans[j]=0; else
{
ans[j]+=1;
} } int t=largest(ans);
if(max<t) max=t; } return max; }
}