#include "stdafx.h"
#include <stdio.h>
#include <memory.h>
#define MAX_LEN 2005
//http://blog.csdn.net/hopeztm/article/details/7870387
//4*6
// 0 1 0 1 0 0
// 0 1 1 0 0 1
// 1 1 1 0 1 0
// 0 0 0 0 0 1
int nRow,nCol;
int matrix[MAX_LEN][MAX_LEN]; // 原始数据
int heights[MAX_LEN][MAX_LEN]; //用这个数据来描述histogram，其中heights[i]表示以第i行走底的histogram，里面的元素表示对应的列的高度
struct Node
{
int height;
int position;
Node(int _height,int _from):height(_height),position(_from)
{
}
Node()
{
}
};
int max(int a,int b)
{
return a > b?a:b;
}
int topID;
Node stack[MAX_LEN];
//栈对应的操作
void push(const Node & t)
{
stack[topID++] = t;
}
const Node top()
{
return stack[topID-1];
}
void pop()
{
topID--;
}
int GetArea(int iRow) // 用单调的栈来枚举其中以第一行做底的histogram所得到的最大的矩形面积
{
topID=0;
push(Node(-1,0));
int i;
int area,maxArea=0;
int position,height;
for(i = 0;i<=nCol;i++)
{
position = i + 1;
if(i == nCol)
{
height = -1;
}
else
{
height = heights[iRow][i];
}
Node t(height,position);
while(top().height > height)
{
t=top();
pop();
area=(position-t.position)*t.height;
if(area > maxArea)
{
maxArea=area;
}
}
push(Node(height,t.position));
}
return maxArea;
}
/*
int main(int argc, char *argv[])
{
while(scanf("%d%d",&nRow,&nCol) != EOF)
{
int i,j;
int b;
for(i=0;i<nRow;i++)
{
for(j=0;j<nCol;j++)
{
scanf("%d",&matrix[i][j]);
}
}
memcpy(heights,matrix,sizeof(matrix));
for(i = 0;i < nCol;i++)
{
for(j=1;j<nRow;j++)
{
if(heights[j][i] !=0)
{
heights[j][i]+=heights[j-1][i];
}
}
}
int maxArea = 0,Area;
for(i=0;i<nRow;i++)
{
Area = GetArea(i);
maxArea=max(maxArea,Area);
}
printf("maxArea:%d\n",maxArea);
}
return 0;
}
*/
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报。
