博客

1102 面积最大的矩形

收藏

关注

有一个正整数的数组，化为直方图，求此直方图包含的最大矩形面积。例如 2,1,5,6,2,3，对应的直方图如下：

面积最大的矩形为5,6组成的宽度为2的矩形，面积为10。

第1行：1个数N，表示数组的长度(0 <= N <= 50000)
第2 - N + 1行：数组元素A[i]。(1 <= A[i] <= 10^9)

输出最大的矩形面积

6
2
1
5
6
2
3

10

题解：维护一个单调递增栈，找出当前元素能够延伸到的最左端，并且不断更新栈顶元素。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
ll a[maxn],n,ans;
stack<int> s;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%lld",&a[i]);
    a[n]=-1;
    for(int i=0;i<=n;i++){
        if(s.empty()||a[i]>a[s.top()]) s.push(i);
        else if(a[i]<a[s.top()]){
            int tmp;
            while(!s.empty()&&a[i]<a[s.top()]){
                ans=max(ans,(i-s.top())*a[s.top()]);
                tmp=s.top();
                s.pop();
            }
            s.push(tmp);
            a[tmp]=a[i];
        }
    }
    printf("%lld\n",ans);
}