Largest Rectangle in a Histogram
这么经典的题硬是等今天碰到了原题现场懵逼两小时才会去补题。。。废话不多说：
题意：截取一个矩形使其面积最大，随你怎么截，反正面积要最大。输出最大面积，注意爆int。
思路：dp或单调队列。核心思路是从一个小矩形往两边扩散，分别找两边第一个小于这个矩形的位置，其中面积就是这个小矩形与区间长度的乘积，我们预处理出所有的小矩形的这两个端点值，然后扫一遍即可更新到最大值。
先看DP怎么做：其实我的理解dp是一种思想，类似dp。我们用l[i],r[i]来表示上述的两个值，然后初始都赋为i。我们更新时只需沿着上一个一直往前找，直到一个数不大于当前的数即可，然后将这个l[i]、r[i]用上一个来更新。
ll a[N],l[N],r[N];
int main()
{
int n;
while(~scanf("%d",&n)&&n)
{
for(int i=1;i<=n;i++)
{
scanf("%I64d",&a[i]);
l[i]=r[i]=i;
}
for(int i=1;i<=n;i++)
{
while(l[i]>1&&a[l[i]-1]>=a[i])
l[i]=l[l[i]-1];
}
for(int i=n;i>=1;i--)
{
while(r[i]<n&&a[r[i]+1]>=a[i])
r[i]=r[r[i]+1];
}
ll ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,a[i]*(r[i]-l[i]+1));
printf("%I64d\n",ans);
}
return 0;
}
单调栈：
说白了也是一种思想，每次对栈顶元素进行操作，如果维护的单增栈，则判断当前元素与栈顶元素，如果大于栈顶元素肯定直接入栈，否者重复出栈操作直到栈顶元素小于当前元素。单减栈同理，是不是很土。重要的还是思想，这种求第一个不大于a或不小于a[i]的位置就很好做了。
ll a[N],l[N],r[N];
int main()
{
int n;
while(~scanf("%d",&n)&&n)
{
for(int i=1; i<=n; i++)
{
scanf("%lld",&a[i]);
l[i]=r[i]=i;
}
stack<ll>q;
for(int i=1; i<=n; i++)
{
while(!q.empty()&&a[i]<=a[q.top()])
{
l[i]=l[q.top()];
q.pop();
}
q.push(i);
}
while(!q.empty()) q.pop();
for(int i=n; i>=1; i--)
{
while(!q.empty()&&a[i]<=a[q.top()])
{
r[i]=r[q.top()];
q.pop();
}
q.push(i);
}
ll ans=0;
for(int i=1; i<=n; i++)
{
ans=max(ans,a[i]*(r[i]-l[i]+1));
}
printf("%lld\n",ans);
}
return 0;
}
思想很重要，学不能致用废矣！