学习目标
- 用单调栈保存还没有找到右侧严格更大值的位置。
- 区分“更大”和“相等”，并说明不存在答案时的
-1。 - 证明每个下标只入栈、出栈各一次。
前置知识与环境
建议先学习第 2 章栈与队列。使用 ISO C++17；开始前可在本目录运行 make doctor。
任务
对每个位置 i，只在下标 j>i 中找最小的、满足 a[j]>a[i] 的 j，输出该位置的值 a[j]。不循环回数组开头；相等值不算更大。
输入格式
第一行 n；第二行 n 个整数。
输出格式
输出每个位置右侧第一个严格更大值；不存在输出 -1。各答案以空格分隔，末尾输出换行。例如 [2,1,2] 输出 -1 2 -1；n=0 只输出空行。
数据范围与限制
0 <= n <= 200000；当n=0时第二行为空，输出空行。- 输入规模不超过
200000，除题面另有说明外整数使用 64 位有符号范围。 - 标准输出只保留题目要求的结果；调试信息写入标准错误。
- 目标算法应为线性或摊还线性时间，辅助空间不超过
O(n)。
边界与验收重点
- 全递增、全递减、相等值和重复的局部峰值。
- 栈内保存下标，以便给之前等待的元素回填答案。
- 右边没有更大值时保留
-1；n=0输出空行。
如何验证
powershell
make doctor
make run
make score未安装 Make 时，在仓库根目录运行：
powershell
pnpm lab:validate -- labs/chapter-02/exercise/E-02-12-next-greater-element
pnpm lab:run -- labs/chapter-02/exercise/E-02-12-next-greater-element
pnpm lab:score -- labs/chapter-02/exercise/E-02-12-next-greater-element思考与复盘
- 为什么读到相等值时不能弹出栈顶？
- 为什么出栈时遇到的当前值一定是该位置右侧第一个严格更大值？
思考题参考
- 题目要求严格大于；等于不满足条件，
[2,2]两个答案都为-1。 - 从左到右扫描，在当前元素之前没有任何满足条件的元素触发该下标出栈。
题解
点击查看题解
思路与不变量
从左到右扫描数组，栈中保存尚未找到答案的位置下标，并保持这些位置对应的值单调不增。当前值 a[i] 到来时，所有栈顶值严格小于它的位置都可以立即确定答案为 a[i]。
算法步骤
- 初始化全部答案为
-1； - 扫描下标
i，反复弹出满足a[stack.top()] < a[i]的位置并回填答案； - 将
i压入栈，等待右侧更大值； - 扫描结束后栈中剩余位置没有符合条件的右侧元素，保留
-1。
正确性说明
位置出栈前，扫描范围内没有更早出现的严格更大值，否则它已经触发出栈；当当前值严格更大时，它又是该位置右侧第一个满足条件的值。因此出栈时回填的值正是题目要求的答案。相等值不会触发出栈，符合“严格更大”。
复杂度分析
- 时间复杂度：
O(n)，每个下标最多入栈和出栈一次； - 额外空间：
O(n)，答案数组和下标栈均为线性规模。
边界注意
- 相等值不能使用
<=弹出，否则会错误地把相等值当作更大值； - 全递减或单元素数组的答案全部为
-1； n=0时直接输出空行。