题目描述
直方图是由在公共基线处对齐的一系列矩形组成的多边形。
矩形具有相等的宽度,但可以具有不同的高度。
现在,请你计算在公共基线处对齐的直方图中最大矩形的面积。
学习单调栈
C++ 代码
#include<iostream>
#include<stack>
#include<math.h>
using namespace std;
#define LL long long
int main(){
int n;
while(cin>>n, n){
stack <int> left;
stack <int> right;
LL arr[n], maxRes = 0;
int ansl[n], ansr[n];
for(int i = 0; i < n; i++){
cin>>arr[i];
}
for(int i = 0; i < n; i++){
int rightIndex = n - i - 1;
int curLeft = arr[i], curRight = arr[rightIndex];
while(!left.empty() && arr[left.top()] >= curLeft) left.pop();
while(!right.empty() && arr[right.top()] >= curRight) right.pop();
if(!left.empty()) ansl[i] = left.top();
else ansl[i] = -1;
if(!right.empty()) ansr[rightIndex] = right.top();
else ansr[rightIndex] = n;
left.push(i);
right.push(rightIndex);
}
for(int i = 0; i < n; i++){
//cout<<"l="<<ansl[i]<<";r="<<ansr[i]<<";arr[i]="<<arr[i]<<";i="<<i<<endl;
LL res = (i-ansl[i]) * arr[i] + (ansr[i] - i) * arr[i] - arr[i];
maxRes = max(maxRes, res);
}
cout<<maxRes<<endl;
}
return 0;
}