发布时间：2024-07-31

悬线法

悬线法的适用范围是单调栈的子集。具体来说，悬线法可以应用于满足以下条件的题目：

需要在扫描序列时维护单调的信息；
可以使用单调栈解决；
不需要在单调栈上二分。

如图所示，在一条水平线上有 n个宽为 1的矩形，求包含于些矩形的最大子矩形面积（图中的阴影部分的面积即所求答案）。
显然，这是一道经典单调栈题目
单调栈代码如下

cpp

void solve(){
    ll n;
    while(cin>>n&&n!=0){
        stack<ll> st;
        vector<ll> a(n+1);
        for(int i=0;i<n;i++)cin>>a[i];
        a[n]=-1;//保证最后全部数出栈
        ll ans=0;
        for(int i=0;i<=n;i++){
            int x=-1;
            while(!st.empty()&&a[st.top()]>a[i]){
                x=st.top();
                st.pop();
                ans=max(ans,1ll*(i-x)*a[x]);
            }
            if(x!=-1){
                a[x]=a[i];
                st.push(x);//关键将准备要插入的块的长度延长至最后一个删除的块，才能确保答案正确
                continue;
            }
            else st.push(i);
        }
        cout<<ans<<"\n";
    }
}

将每一个高度看作一条悬线，可以左右移动，则该高度对应的长度即为左右可移动的长度
定义 $l_i$ 为第 $i$ 个所能到达的左边界

$l_i=1$ ,说明到达最左端
$若a_i>a_{l_i-1}$ ,则说明不能扩展
否则可以继续扩展,且 $l_i=l_{l_i-1}$
右边界r同理

cpp

void solve(){
    ll n;
    while(cin>>n&&n!=0){
        vector<ll> a(n+1),l(n+1),r(n+1);
        iota(l.begin()+1,l.end(),1);
        iota(r.begin()+1,r.end(),1);
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=2;i<=n;i++){
            while(l[i]>1&&a[i]<=a[l[i]-1])l[i]=l[l[i]-1];
        }
        for(int i=n-1;i>=1;i--){
            while(r[i]<n&&a[i]<=a[r[i]+1])r[i]=r[r[i]+1];
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            ans=max(ans,(r[i]-l[i]+1)*a[i]);
        }
        cout<<ans<<"\n";
    }
}

悬线法 ​

悬线法