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

题目描述

小欧想要构造一个合法的括号序列满足以下条件:
1.括号序列长度恰好为 2 × n 。
2.括号序列的嵌套层数最大值为 r 。
括号嵌套层数是指在一个字符串中,以左括号 "(" 和右括号 ")" 形成的括号对的最大嵌套深度。
例如,在字符串 "((())())" 中,括号嵌套层数最大值为 3。

输入输出

输入描述
一行两个整数 n, r(1 ≤ r ≤ n ≤ 10^5) 。
输出描述
一行一个字符串表示括号序列。若有多种构造方案,输出任意一个即可。

样例共 1 组

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

算法解析依据一般

考点:栈

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

题目画像

  • 数据规模:n ≤ 1e5
  • 元素值域:r ≤ 1e5(注意整数类型选择,避免溢出)
  • 复杂度门槛:只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:栈

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 n ≤ 1e5,只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 元素值域最大到 1e5 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

样例

样例 1

  • 输入:3 2
  • 输出:()(())

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

本题来源:2024年秋招-OPPO-后端岗笔试。

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