题目描述

难度分:$1400$

输入一个长度$\leq 10^6$的括号字符串$s$。

输出$s$的最长合法括号子序列的长度。

注：子序列不一定连续。

输入样例$1$

(()))(

输出样例$1$

4

输入样例$2$

((()())

输出样例$2$

6

算法

贪心

准备一个变量$left$，用来记录遍历过程中扫过的左括号数目，然后开始遍历$s$串，遇到左括号就对$left$自增，遇到右括号才开始结算有效括号子序列的长度。

当遇到右括号时，如果$left \gt 0$，就将当前右括号与前面的一个左括号配对，此时有效括号子序列的长度会增加$2$，之所以不在左括号时更新子序列长度，是因为不确定左括号是否能有右括号与其配对。这样一来，遍历完$s$串后就能得到答案。

复杂度分析

时间复杂度

仅遍历了一遍原字符串$s$，时间复杂度为$O(n)$。

空间复杂度

除了输入的$s$串之外，仅使用了有限几个变量，所以额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1000010;
char s[N];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    int left = 0, ans = 0;
    for(int i = 1; i <= n; i++) {
        if(s[i] == '(') {
            left++;
        }else {
            if(left) {
                left--;
                ans += 2;
            }
        }
    }
    printf("%d", ans);
    return 0;
}