ACWing 150 括号画家

Problem

Solution

发现括号序列便想到栈。你一定做过下面这样的题目:

给一个长度为\(n\)的括号序列,定义:

  • (),[],{}是合法的。
  • 如果A是合法的,那么(A),[A],{A}也是合法的。
  • 如果A,B是合法的,那么AB也是合法的。
    判断这个序列合不合法,时间复杂度要求在\(\mathcal{O}(n)\)内。

这个当然是很好想了。对于每个字符串,如果是左括号,就直接进栈,如果是右括号,判断栈顶的左括号是否与之匹配,不是则不合法。最后判断栈是否为空。

考虑到原问题,我们发现,对于一端合法的子序列。如果将其单独用一个栈来维护,那最后一定是空栈。如果放到主栈中,在从加入这个子序列之前和加完之后是一模一样的(因为全部弹出了)。所以,在第\(i\)个字符时的当前最长合法序列为\(S[top + 1 \sim i]\),取最大即可。

时间复杂度\(\mathcal{O}(n)\)。

# include <bits/stdc++.h>
using namespace std;
const int N = 100002;
int k = 0;
char s[N];
int ans = 0;
stack <int> q;
int main(void)
{   
    scanf("%s",s + 1);
    int n = strlen(s + 1);
    // printf("n = %d\n",n);
    for(int i = 1; i <= n; i++)
    {
        if(!q.empty())
        {
            char top = s[q.top()];
            if(s[i] == ')' && top == '(' || s[i] == ']' && top == '[' || s[i] == '}' && top == '{')
            {
                q.pop();
            }
            else q.push(i);
        }
        else q.push(i);
        if(!q.empty()) 
        {
            ans = max(ans,i - q.top());
        }
        else
        {
            ans = max(ans,i);
        }
    }
    printf("%d\n",ans);
    return 0;
}
上一篇:力扣每日一题150 逆波兰式


下一篇:练习2-4 温度转换