# 《Largest Rectangle in a Histogram》

1 2 3 4 5 6.

sum = 6*1.

sum = 5*2

sum = 4*3

sum = 3*4

sum = 2*5

sum = 1*6

```#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double ld;
typedef pair<LL,int> pii;
const int N = 1e5+5;
const int M = 1e6+5;
const LL Mod = 1e9+7;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define INM INT_MIN
#define dbg(ax) cout << "now this num is " << ax << endl;
{
LL x = 0,f = 1;char c = getchar();
while(c < ‘0‘ || c > ‘9‘){if(c == ‘-‘) f = -1;c = getchar();}
while(c >= ‘0‘ && c <= ‘9‘){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
return x*f;
}
LL S[N],w[N],h[N];
int main()
{
int n;
{
for(int i = 1;i <= n;++i) h[i] = read();
int top = 0;
LL ans = 0;
h[n+1] = 0;
for(int i = 1;i <= n+1;++i)
{
if(h[i] > S[top])
{
S[++top] = h[i];
w[top] = 1;
}
else
{
LL width = 0;
while(top != 0 && S[top] > h[i])
{
width += w[top];
ans = max(ans,width*S[top]);
top--;
}
S[++top] = h[i];
w[top] = width+1;
}
}
printf("%lld\n",ans);
}
system("pause");
return 0;
}```
View Code

《Largest Rectangle in a Histogram》

(0)
(0)