题目描述：
/**
给定一组非负整数组成的数组h，代表一组柱状图的高度，
其中每个柱子的宽度都为1。
在这组柱状图中找到能组成的最大矩形的面积（如图所示）。
入参h为一个整型数组，代表每个柱子的高度，返回面积的值。
输入描述:
输入包括两行,第一行包含一个整数n(1 ≤ n ≤ 10000)
第二行包括n个整数,表示h数组中的每个值,h_i(1 ≤ h_i ≤ 1,000,000)
输出描述:
输出一个整数,表示最大的矩阵面积。
输入例子1:
6
2 1 5 6 2 3
输出例子1:
10
*/
思路如下：
维护一个单调递增的堆
更新left[i]表示i位置向左可以延伸多少
right[i]同理
代码如下：
#include<stdio.h>
#include<iostream>
#include<climits>
#include<stack>
#define MAX_N 10005
typedef long long ll;
using namespace std;
int height[MAX_N], lnum[MAX_N], rnum[MAX_N];
int main(){
int n;
stack<int> st;
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", height+i);
lnum[0] = 0;
for(int i=0; i<n; i++){
if(st.empty() || height[i]>height[st.top()]){
st.push(i);
}
else{
while(!st.empty() && height[i]<=height[st.top()])
st.pop();
if(st.empty())
lnum[i] = i;
else
lnum[i] = i-1-st.top();
st.push(i);
}
}
//清空
while(!st.empty())
st.pop();
rnum[n-1] = 0;
for(int i=n-1; i>=0; i--){
if(st.empty() || height[i]>height[st.top()]){
st.push(i);
}
else{
while(!st.empty() && height[i]<=height[st.top()])
st.pop();
if(st.empty())
rnum[i] = n-(i+1);
else
rnum[i] = st.top()-i-1;
st.push(i);
}
}
ll res = LLONG_MIN;
for(int i=0; i<n; i++){
res = max(res, (ll)(lnum[i]+rnum[i]+1)*(ll)height[i]);
}
printf("%lld", res);
return 0;
}
