美团 · 栈 · 算法编程题
美团 栈 n ≤ 200000 时限 5 秒 / 1024 MB

题目描述

给定一个长度为 n 的数组 a ，我们定义一个区间 [l,r] 是好的，当且仅当这个区间可以分成两个非空的子序列，元素之间相对顺序不变，使得这两个子序列都是严格单调递增子序列。
对于给出多次询问，你需要问答区间是不是好区间。

输入输出

输入描述
第一行一个整数 T(1≤ T≤ 20000) ，表示有 T 次询问。
对于每次询问，第一行两个整数 n,q(2≤ n,q≤ 2× 10^5) ，第二行 n 个整数 a_i(1≤ a_i≤ 10^9) ，表示数组 a 。
接下来 q 行，每行两个整数 l,r(1≤ l< r≤ n) ，表示询问的区间。
单个测试文件保证 n 和 q 的和均不超过 2× 10^5 。
输出描述
对于每次询问，输出一行，如果区间是好区间，输出 YES ，否则输出 NO 。

样例共 1 组

样例 1
输入
2
4 2
1 2 3 3
1 3
1 2
5 3
4 5 4 5 3
1 4
1 5
2 4
输出
YES
YES
YES
NO
YES

算法解析依据充分

考点：数组 · 单调栈

数据规模 n ≤ 200000 ｜ 限制 5 秒 / 1024MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 200000，q ≤ 200000，T ≤ 20000
  • 元素值域：a_i ≤ 1e9（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
  • 源站时限：5 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：栈

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

思路框架（栈 通法 · 非本题专属）

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

实现要点：Python 用 list 当栈（append/pop）；判断栈空再取栈顶。

复杂度：时间 O(n) ｜ 空间 O(n)

该范式的通法易错点

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

对照本题

  • 数据规模 n ≤ 200000，只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
  • 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入：2 / 4 2 / 1 2 3 3 / 1 3 / 1 2 / 5 3 / 4 5 4 5 3 / 1 4 / 1 5 / 2 4
  • 输出：YES / YES / YES / NO / YES

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

本题来源：2025年春招-美团-技术岗笔试；2025年春招-美团-算法岗笔试。

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