小欧拿到了一个只包含'('和')'的字符串,她有以下两种操作:
1. 用"("代替一对括号:"()"。
2. 用")"代替一对括号:"()"。
请注意,只有相邻的括号字符才可以操作。
小欧想知道,若干次操作以后,该字符串的最短长度是多少?一个只包含'('和')'两种字符的字符串。长度不超过200000。
一个整数,代表若干次操作后,字符串的最短长度。
()
1
)(
2
考点:栈
数据规模 n ≤ 200000 | 限制 1 秒 / 256MB | 标准输入输出
推荐方向:栈
本题切入点
用栈做括号匹配,能配对的 () 都可被消去,最后剩下的就是无法消掉的最短长度。
后进先出的结构天然适合处理嵌套、匹配与「最近的更大/更小」问题。
思路框架(栈 通法 · 非本题专属)
实现要点:Python 用 list 当栈(append/pop);判断栈空再取栈顶。
复杂度:时间 O(n) | 空间 O(n)
该范式的通法易错点
对照本题
样例 1
()1样例 2
)(2解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:2023年OPPO秋招算法岗笔试。