OPPO · 栈 · 算法编程题
OPPO n ≤ 200000 时限 1 秒 / 256 MB

题目描述

小欧拿到了一个只包含'('和')'的字符串,她有以下两种操作:
1. 用"("代替一对括号:"()"。
2. 用")"代替一对括号:"()"。
请注意,只有相邻的括号字符才可以操作。
小欧想知道,若干次操作以后,该字符串的最短长度是多少?

输入输出

输入描述
一个只包含'('和')'两种字符的字符串。长度不超过200000。
输出描述
一个整数,代表若干次操作后,字符串的最短长度。

样例共 2 组

样例 1
输入
()
输出
1
样例 2
输入
)(
输出
2

算法解析依据充分

考点:栈

数据规模 n ≤ 200000 | 限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 数据规模:n ≤ 200000
  • 复杂度门槛:只允许 O(n) 或 O(n log n),且常数要小(注意读入效率)。
  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

推荐方向:栈

本题切入点

用栈做括号匹配,能配对的 () 都可被消去,最后剩下的就是无法消掉的最短长度。

后进先出的结构天然适合处理嵌套、匹配与「最近的更大/更小」问题。

思路框架(栈 通法 · 非本题专属)

  1. 括号匹配:遇左括号入栈,遇右括号检查栈顶是否配对。
  2. 单调栈:从左到右扫,维持栈内单调,遇到破坏单调性的元素就弹栈并结算答案。
  3. 每个元素最多进出栈各一次,总复杂度 O(n)。

实现要点:Python 用 list 当栈(append/pop);判断栈空再取栈顶。

复杂度:时间 O(n) | 空间 O(n)

该范式的通法易错点

  • 栈空时取栈顶。
  • 弹栈时机的判断条件写反。

对照本题

  • 数据规模 n ≤ 200000,只允许 O(n) 或 O(n log n),且常数要小(注意读入效率)。

题目给出的提示

  • 只有相邻的括号字符才可以操作

样例

样例 1

  • 输入:()
  • 输出:1

样例 2

  • 输入:)(
  • 输出:2

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:2023年OPPO秋招算法岗笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解