括号画家

题目描述

达达画了一行由 ( )、[ ]、{ } 组成的括号序列，长度 $N \leqslant 10^5$ 。美观（合法）序列定义为：空串美观； $A$ 美观则 (A)、[A]、{A} 美观； $A,B$ 都美观则 $AB$ 美观。求最长的美观连续子段长度。输入一行括号字符串，输出一个整数表示答案。样例输入 ({({(({()}})}{())})})[){{{([)()((()]]}])[{)]}{[}{)，样例输出 4。

思路

用栈保存尚未配对的左括号下标，barrier 记最近一个失配右括号的下标。左括号入栈；右括号若与栈顶匹配就弹栈，此时以当前位置结尾的最长合法子段左端是新栈顶（栈空时为 barrier），用它更新答案；若失配则该右括号成为新 barrier 并清空栈（配对不能交叉）。每个下标至多进出栈一次，时间 $O(N)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 11:55
# update_at: 2026-10-01 11:54

import sys

PAIR = {')': '(', ']': '[', '}': '{'}  # 右括号 → 它唯一能配上的左括号


def longest_valid(s: str) -> int:
    """最长的合法括号子段长度：栈里只存尚未配对的左括号下标。"""
    ans = 0
    stack: list[int] = []
    barrier = -1  # 最近一个无法配对的右括号下标，合法子段不可能跨过它
    for i, ch in enumerate(s):
        opener = PAIR.get(ch)
        if opener is None:  # 左括号：下标入栈，等待将来的右括号
            stack.append(i)
        elif stack and s[stack[-1]] == opener:
            # 与栈顶左括号配对：以 i 结尾的合法子段，左端紧贴"栈内更靠下的
            # 未配对左括号"或壁垒，二者之间恰好是一段合法序列
            stack.pop()
            left = stack[-1] if stack else barrier
            ans = max(ans, i - left)
        else:
            # 配不上的右括号：任何包含它的子段都非法，它成为新壁垒，
            # 且它之前入栈的左括号再也配不上（配对不能交叉），清空栈
            stack.clear()
            barrier = i
    return ans


def solve() -> None:
    s = sys.stdin.read().strip()
    print(longest_valid(s))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:32
 * update_at: 2026-10-06 11:32
 */
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 100005; // 字符串长度上限

char s[MAXN];    // 输入的括号序列
int stk[MAXN];   // 栈：存放尚未配对的左括号下标
int top;         // 栈顶指针，栈内元素为 stk[1..top]

// 返回右括号 ch 对应的左括号；若不是右括号则返回 0
char match_left(char ch) {
    if (ch == ')') return '(';
    if (ch == ']') return '[';
    if (ch == '}') return '{';
    return 0;
}

int main() {
    if (scanf("%s", s + 1) != 1) return 0; // 从下标 1 开始读入
    int n = strlen(s + 1);

    int ans = 0;
    int barrier = 0; // 最近一个无法配对的右括号下标，合法子段不能跨过它
    top = 0;
    for (int i = 1; i <= n; i++) {
        char left_ch = match_left(s[i]);
        if (left_ch == 0) {
            // 左括号：下标入栈，等待将来的右括号
            stk[++top] = i;
        } else if (top > 0 && s[stk[top]] == left_ch) {
            // 与栈顶左括号配对：以 i 结尾的合法子段左端紧靠栈内更靠下的
            // 未配对左括号（或断点）
            top--;
            int left = (top > 0) ? stk[top] : barrier;
            if (i - left > ans) ans = i - left;
        } else {
            // 配不上的右括号：成为新断点，之前的左括号因配对不能交叉而全部作废
            top = 0;
            barrier = i;
        }
    }
    printf("%d\n", ans);
    return 0;
}

目录

题目描述

思路

参考代码