city largest rectangle in a histogram
从1-n遍历，取出每次以i为右边界（完全取到）最大的面积。
显然，i最多可以延伸到的地方是比他高或者等的第一个长条，算出每次面积的最大，再一起取max
单调栈即可。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=100005; ll a[maxn],w[maxn];int q[maxn]; int n; void work() { int r=0;ll maxv=0; a[n+1]=0; //注意啊最后一次也要搞的 for(int i=1;i<=n+1;i++) { ll width=0; while(r&&a[q[r]]>=a[i]) { width+=w[q[r]]; maxv=max(maxv,a[q[r]]*width); r--; } q[++r]=i;w[i]=width+1; } printf("%lld\n",maxv); } int main() { while(1) { scanf("%d",&n); if(n==0) break; for(int i=1;i<=n;i++) scanf("%lld",&a[i]); work(); } return 0; }后面一题是这个的扩展，多一层循环。
#include <bits/stdc++.h> using namespace std; const int maxn=1005; int n,m;char a[maxn][maxn]; int h[maxn],q[maxn],w[maxn]; int work() { int r=0;h[m+1]=0;int maxv=0; for(int i=1;i<=m+1;i++) { int width=0; while(r&&h[q[r]]>=h[i]) { width+=w[q[r]]; maxv=max(maxv,h[q[r]]*width); r--; } q[++r]=i;w[i]=width+1; } return maxv; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } int ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(a[i][j]=='F') h[j]+=1; else h[j]=0; } ans=max(ans,work()); } printf("%d",ans*3); return 0; }再看这一题，单调队列，只要转化成前缀和，就发现求得实际上是区间内最小的东西。
#include <bits/stdc++.h> using namespace std; const int maxn=300005; int n,m,sum[maxn],q[maxn]; int a[maxn]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]; int l=1,r=0;int maxv=0;q[1]=0;//注意下初始化! for(int i=1;i<=n;i++) { while(i-q[l]>m&&l<=r) l++; maxv=max(maxv,sum[i]-sum[q[l]]); while(l<=r&&sum[i]<=sum[q[r]]) r--; q[++r]=i; } printf("%d",maxv); return 0; }
