难度：3级算法题
第1行：1个数N，表示数组的长度(0 <= N <= 50000) 第2 - N + 1行：数组元素A[i]。(1 <= A[i] <= 10^9)
输出最大的矩形面积
6 2 1 5 6 2 3
10
思路：
一：DP:
dp1[i]: 表示 从a[i]向左边连续不小于 a[i]高度的最小下标值
dp2[i]: 表示 从a[i]向右边连续不小于 a[i]高度的最大下标值
对于 dp1[]: 若 a[i]>a[i-1] 则 dp1[i]=i;否则 dp1[i]=dp1[i-1],然后继续和 a[dp1[i-1]-1] 比较 ，若a[i]小于等于则 继续反复比较直到 a[i]对于 a[x] 或者x<=0;(a[1->n])为止。对于dp2[]也是如此只不过是和 右边的比较
这样就知道了 对于 a[i]为高的矩形的宽度 w=dp2[i]-dp1[i]+1，因此可得到最大矩形面积
二：stack
用两个栈 stack1,stack2分别记录 以a[i]为高的矩形的宽的a[i]左右边长度。
对于 stack1 记录 以a[i]为高的矩形的宽的a[i]左边长度。对于 a[i],若 a[i]>stack1.top()则入栈，说明左边长度为L[i]=0；否则 L[i]+=L[stack1.top()]+1; 再出栈，a[i]继续和 栈头比较
对于 stack2也是如此，这样 就知道 以a[i]为高的矩形的宽的a[i]左右边长度L[i],R[i],ans=max{a[i]*(R[i]+L[i]+1)}
三: stack
第二种是用二个栈来计算 L[i],R[i],实际上可以只用 一个栈就可以维护。
栈stack 保存a[i]的最左边界下标t，其下标对应的a[t]=a[i],这样只要找到 a[i]的最右下标即可求出其矩形面积.
遍历 a[i],若a[i]>a[stack.top()],则 a[i]对应的矩形最左端就是其自己，因此只要入栈即可
而若 a[i]<=a[stack.top()],则 要找到a[i]对应的矩形最左端t. 那么就要与 栈顶 ti 对于的a[ti]比较，若a[i]<=a[ti],则令t=ti,
而对于a[ti]来说，i就是它的最右端，此时保存它的矩形面积 ans=max(ans,a[t]*(i-t));
直到 a[i]>a[ti] 此时 t就是 最左端下标; 修改 令 a[t]=a[i],再将 t 入栈，在所有a[]入栈后，还要将栈中的元素求其面积，因此只要将 a[n+1]=0也进行比较即可。（a[1->n]）
Code 1:
#include<iostream>
using namespace std;
typedef long long LL;
const int MAX_N=50005;
int n;
LL a[MAX_N];
int dp1[MAX_N],dp2[MAX_N];
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>a[i];
dp1[i]=dp2[i]=i;
}
for(int i=1;i<=n;++i)
{
for(int p=i-1;p&&a[i]<=a[p];p=dp1[p]-1)
dp1[i]=dp1[p];
for(int p=n-i+1;p<=n&&a[n-i]<=a[p];p=dp2[p]+1)
dp2[n-i]=dp2[p];
}
LL ans=0;
for(int i=1;i<=n;++i)
ans=max(ans,a[i]*(dp2[i]-dp1[i]+1));
cout<<ans<<endl;
return 0;
}Code 2:
#include<iostream>
#include<stack>
using namespace std;
typedef long long LL;
struct node{
LL x;
int id;
};
const int MAX_N=50005;
int n;
LL a[MAX_N];
int L[MAX_N],R[MAX_N];
stack<node> sta1,sta2;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=0;i<n;++i)
cin>>a[i];
for(int i=0;i<n;++i)
{
while(!sta1.empty()){
node t=sta1.top();
if(a[i]<=t.x){
sta1.pop();
L[i]+=L[t.id]+1;
}else break;
}
sta1.push(node{a[i],i});
while(!sta2.empty()){
node t=sta2.top();
if(a[n-i-1]<=t.x){
sta2.pop();
R[n-i-1]+=R[t.id]+1;
}else break;
}
sta2.push(node{a[n-i-1],n-i-1});
}
LL ans=0;
for(int i=0;i<n;++i)
ans=max(ans,a[i]*(L[i]+R[i]+1));
cout<<ans<<endl;
return 0;
}Code3:
#include<iostream>
#include<stack>
using namespace std;
typedef long long LL;
const int MAX_N=50005;
int n;
LL a[MAX_N],ans;
stack<int> sta;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
for(int i=1;i<=n+1;++i) //a[n+1]求出栈中所有点的矩阵面积
if(sta.empty()||a[i]>a[sta.top()]){
sta.push(i);
}else if(a[i]<a[sta.top()]){
int t=0;
while(!sta.empty()){
if(a[i]<=a[sta.top()]){
t=sta.top();
sta.pop();
ans=max(ans,a[t]*(i-t));
}else break;
}
sta.push(t);
a[t]=a[i];
}
cout<<ans<<endl;
return 0;
}