题解：P10472 括号画家 | O(n) 模拟做法

许卿安 · 2025-05-14 13:02:57 · 题解

我们充分发扬人类智慧，在用栈模拟的时候把当前合法括号序列长度也压到栈里。若当前括号可以匹配：如果栈中前面一个为长度，那么将长度合并再压进去，否则直接将 2 压进栈中。若当前括号无法匹配，则直接压入栈中。最后取栈内元素最大值即可。

要注意栈为空的情况，防止 RE。时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
#define pci pair<char,int>
#define mkp make_pair
#define w(x) s.push(mkp(x,0))
#define e(x) s.push(mkp('.',x))

stack<pci> s;

void debug(){
    stack<pci> ss{s};
    string out="";
    while(!ss.empty()){
        pci sse=ss.top();
        if(sse.second) out+=to_string(sse.second);
        else out+=sse.first;
        ss.pop();
    }
    for(int i=out.length(); i>=0; i--) cout<<out[i];
    cout<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string a;cin>>a;int l=a.length();
    for(int i=0; i<l; i++){
        //debug();
        char x=a[i];
        if(s.empty()){
            w(x);
            continue;
        }
        pci frt=s.top();
        char fr=frt.first;int se=frt.second;
        bool isd=0;
        if(se){
            s.pop();
            if(s.empty()){
                e(se);w(x);
                continue;
            }
            frt=s.top();
            fr=frt.first;
            isd=1;
        }
        if((fr=='(' && x==')') || (fr=='[' && x==']') || (fr=='{' && x=='}')){
            s.pop();
            if(s.empty()){
                e(se+2);
                continue;
            }
            if(s.top().second){
                se+=s.top().second;
                s.pop();
            }
            e(se+2);
            continue;
        }
        if(isd) e(se);
        w(x);
    }
    //debug();
    int mxl=0;
    while(!s.empty()){
        if(s.top().second) mxl=max(mxl,s.top().second);
        s.pop();
    }
    cout<<mxl;
    return 0;
}