题目传送门：
POJ-2259
题目大意：
给出一个柱状统计图，该统计图由多个宽度为1高度不一的矩形构成，问图中包含最大的矩形面积是多少
分析：
每个矩形都有不一样的高度，要让矩形尽可能大，则应该在高度一定的情况下尽可能的向两边延伸宽度
若以每个矩形的高为最终的高，然后暴力算出宽度，则时间复杂度较大。每个矩形的高度向左向右均是
扩展到第一个比他矮的矩形处（比他矮的之后就扩展不过去了少了上面的一截），因此找到向左向右第
一个比他小的值即可。用单调递增栈维护高，算出每个值扩展范围，然后比较得出结果
代码：
#include#include #include #include using namespace std;const int MAX=100009;typedef long long ll;int l[MAX],r[MAX];ll a[MAX];int n;stack st;int main(){ while(~scanf("%d",&n)&&n) { for(int i=1;i<=n;i++)scanf("%lld",&a[i]); a[0]=a[n+1]=-1; //n+1插入-1让最后栈中元素都弹出 for(int i=0;i<=n+1;i++) { while(!st.empty()&&a[st.top()] > a[i])//当插入元素比栈顶元素小 { //表示栈顶元素向右只能扩展至该元素 更新右边界 r[st.top()]=i; st.pop(); } if(!st.empty())l[i]=st.top()+1; //单调递增栈，因此入栈后，栈内的一个元素比插入的元素 st.push(i); //小，插入元素向左只能扩展到该处 ，更新左边界 } ll ans=0; for(int i=1;i<=n;i++) { if(ans<(r[i]-l[i])*a[i]) ans=(r[i]-l[i])*a[i]; } printf("%lld\n",ans); } return 0;}
POJ-3494
题目大意：
给出一个由0和1组成的n*m的矩阵，问矩阵中全由1组成的最大矩行是多大
分析：
可以发现该题和上面很相似，可以将问题转化为求n个直方图的最大矩形面积，即将n*m的矩阵看成n个以
第i行为底的直方图。
例如 3 3
1 1 1 1 1 1
1 0 1 看成 2 0 2 这样分别对每行求最大矩形面积即可求出最终答案
1 1 1 3 1 3
代码：
#include#include #include #include using namespace std;const int MAX=2009;int n,m;int h[MAX][MAX],l[MAX],r[MAX];stack st;int main(){ while(~scanf("%d%d",&n,&m)) { int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&h[i][j]); if(h[i][j]&&i!=1) h[i][j]+=h[i-1][j]; //处理，转化为n个直方图 } for(int i=1;i<=n;i++) { for(int j=0;j<=m+1;j++) { h[i][0]=h[i][m+1]=-1; while(!st.empty()&&h[i][st.top()] > h[i][j]) { //插入元素小于栈顶元素，栈顶元素扩展右边界为j，弹出栈顶元素 r[st.top()]=j;//当栈顶小于h[i][j]时 j入栈 使栈单调递增 st.pop(); } if(!st.empty()) l[j] = st.top()+1;//这时j的左边界为之前栈顶元素所在位置 st.push(j); } for(int j=1;j<=n;j++) ans=max(ans,h[i][j]*(r[j]-l[j])); } printf("%d\n",ans); } return 0;}