c++

//
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 10;
const int INF = 0x3f;
LL n, a[MAXN];
LL stack[MAXN];
LL l[MAXN], r[MAXN], top = 0;
int main()
{
	start:cin >> n;
	if(n == 0)return 0;
	for (int i = 0;i < n; i++)
	{
		cin >> a[i];
	}
	top = 0;
	a[0] = -1;
	for(int i = 1;i <= n; i++)
	{
		while(top >= 0 && a[i] <= a[ stack[top - 1] ])
			top--;
		l[i] = top == 0 ? 0 : (stack[top - 1] + 1);
		stack[top++] = i;
	}
	top = 0;
	a[0] = -1;
	for(int i = n - 1;i >= 0; i--)
	{
		while(top > 0 && a[i] <= a[ stack[top - 1] ])
			top--;
		r[i] = top == 0 ? 0 : (stack[top - 1]);
		stack[top++] = i;
	}
	LL ans = 0;
	for(int i = 1;i <= n;i++){
		//cout << l[i] << ' ' << r[i] << ' ' << a[i] << endl;
		ans = max(ans, (r[i] - l[i]) * a[i]);
	}
	cout << ans << endl;
	goto start;
}

C++:

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int q[100001];

int a[100001];

int n,t;

int ll;

//int h[100001];

int l[100001];

int r[100001];

void make(int an[100001])

{ //int l=1;

ll=0;

a[0]=-1;

for(int i=1;i<=n;i++)

{

	while(a[q[ll]]>=a[i])

	{

		ll--;

	}

	an[i]=q[ll];

	q[++ll]=i;

}

}

long long maxn;

int main()

{

while(scanf("%d",&n))

{

	if(n==0)

	{

		return 0;

	}

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&a[i]);

	}

	a[0]=-1;

	make(l);

	reverse(a+1,a+1+n);

	make(r);

	//int j=n;

	maxn=0;

	for(int i=1,j=n;i<=n;i++,j--)

	{

		maxn=max(maxn,a[i]*(n-l[j]-r[i]+1-(long long)(1)));

	//	j--;

	}

	printf("%lld\n",maxn);

}

}

C++ :

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>

using namespace std;
typedef long long ll;
const int N = 1e5 + 5;

int n;
int h[N], q[N], l[N], r[N];

void get(int bound[N])
{
    int tt = 0;
    h[0] = -1;
    for(int i = 1; i <= n; i ++ ){
        while(h[q[tt]] >= h[i]) tt -- ;
        bound[i] = q[tt];
        q[ ++ tt] = i;
    }
}

int main()
{
    while(cin >> n, n){
        for(int i = 1; i <= n; i ++ )
            cin >> h[i];
        //立一个标兵在队头
        h[0] = -1;
        get(l);
        reverse(h + 1, h + n + 1);
        get(r);

        ll res = 0;
        //因为之前翻转了一下，所有原本的下标变成了对称位置的下标，1ll是long long 形式的1
        for(int i = 1, j = n; i <= n; i ++, j -- )
            res = max(res, h[i] * (n + 1 - l[j] - r[i] - 1ll));
        cout << res << endl;
    }
    return 0;
}

因为对于一个高度 $h_i$， 我们往左边一直以这个高度延伸，直到不行，再往右边进行一样的操作

那么什么时候不行呢，就是当想要继续延伸的块高度比$h_i$低

左边的极限就是 $h_l \ \ (h_{l-1}<h_i)$ 右边的极限就是 $h_r \ \ (h_{r+1}<h_i)$

那么以 $i$ 为原点往左右两边延伸的最大面积就是$(r-l+1)*h_i$

我们使用单调栈即可求出 $l-1$ 和 $r+1$，我们暂时记为 $ans1$ 和 $ans2$

那么上述提到的面积就是$(ans2-ans1-1)*h_i$ 自己推导一下就知道了

---

AC CODE

#include <bits/stdc++.h> 
using namespace std;
const long long N = 1e5+10,INF = 0x3f3f3f3f;
long long a[N],ans[N],ans2[N],st[N],n,top,res,tmp;
void calc1(){
	for(long long i = 1; i <= n; i++){
		while(top>0&&a[i]<=a[st[top]])top--;
		ans[i]=st[top];st[++top]=i;
	}//单调栈模版，但是>=改成<=以达到效果 
}
void calc2(){
	for(long long i = n; i >= 1; i--){
		while(top>0&&a[i]<=a[st[top]])top--;
		ans2[i]=st[top];st[++top]=i;
	}//单调栈模版，但是>=改成<=以达到效果 
}
void solve(){
	cin >> n;
	if(n==0)exit(0);
	top = 0, res = 0, a[0]=a[n+1]=-INF;
	for(long long i = 1; i <= n; i++)cin >> a[i];
	top = 0;st[++top]=0;calc1();//计算ans1 
	top = 0;st[++top]=n+1;calc2();//计算ans2 
	for(long long i = 1; i <= n; i++)res = max(res,(ans2[i]-ans[i]-1)*a[i]);
	cout << res << '\n';
}
signed main(){
	while(1+1==2)solve();
	return 0;
}//完美30行结束 

思路:

我们找到左边第一个比他小和右边第一个比它小的,就可以得知这个高度的矩形的宽**

代码:

#include<iostream>
#include<stack>
#define int long long
using namespace std;
stack<int> st;
int h[100005],n,to,l[100005],r[100005],ans;
signed main(){
    while(cin>>n,n){
        for(int i=1;i<=n;i++) cin>>h[i];
        h[0]=-1;
        st.push(0);
        for(int i=1;i<=n;i++){
            while(!st.empty()&&h[i]<=h[st.top()]) st.pop();
            l[i]=st.top();
            st.push(i);
        }
        while(!st.empty()) st.pop();
        h[n+1]=-1;
        st.push(n+1);
        for(int i=n;i>=1;i--){
            while(!st.empty()&&h[i]<=h[st.top()]) st.pop();
            r[i]=st.top();
            st.push(i);
        }
        ans=0;
        for(int i=1;i<=n;i++){
            ans=max(ans,(r[i]-l[i]-1)*h[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

#include<cstdio> #include<stack> #include<iostream> #include<algorithm> using namespace std; int n,h[100000],ans=0,x; stack<int>st; bool va(int xx){ if(st.empty()){ return false; } else return st.top()>h[xx]; } int main(){ while(cin>>n &&n){ for(int i=1;i<=n;i++){ scanf("%d",&h[i]); } h[n+1]=-1; st.push(h[1]); for(int i=2;i<=n+1;i++){ x=0; while(va(i)){ x++; ans=max(x*st.top(),ans); st.pop(); } st.push(h[i]); } printf("%d\n",ans);} }

本体思路太蒟蒻

#include<stdio.h> #include<string.h> #include<stack> using namespace std; typedef long long ll; const int N = 1e5 + 5; ll l[N], r[N]; ll a[N]; int n; stack<ll> s; int main(){ while(scanf("%d",&n) && n){ while(!s.empty()) s.pop(); for(int i=1; i<=n; ++i){ scanf("%lld",&a[i]); l[i] = r[i] = i; } a[0] = a[n+1] = -1;

	for(int i=1; i<=n; ++i){
		while(!s.empty() && a[i] <= a[s.top()])
	    s.pop();
	    if(s.empty()) l[i] = 0;
	    else  l[i] = s.top();
	    s.push(i);
	}
	
	while(!s.empty())  s.pop();

	for(int i=n; i>=1; --i){
		while(!s.empty() && a[i] <= a[s.top()])
	    s.pop();
	    if(s.empty())  r[i] = n+1;
    	else  r[i] = s.top();
	    s.push(i);
	}

	ll sum, max = -1;
    for(int i=1; i<=n; ++i){
        sum = (r[i] - l[i] - 1) * a[i];
        if(sum > max) max = sum;
    }
    printf("%lld\n",max);
}
return 0;

}