学习目标

• 用单调栈保存尚未找到右侧严格更小值的下标。
• 正确处理相等值与不存在答案的 -1。
• 证明线性扫描时每个位置最多入栈、出栈各一次。

前置知识与环境

建议先学习第 2 章栈与队列。使用 ISO C++17；开始前可在本目录运行 make doctor。

任务

对每个位置 i，在右侧下标 j>i 中找最小的、满足 a[j]<a[i] 的 j，输出值 a[j]。不循环回数组开头；相等值不算更小。

输入格式

第一行 n；第二行 n 个整数。

输出格式

输出每个位置右侧第一个严格更小值；不存在输出 -1。各答案以空格分隔，末尾换行。例如 [2,1,2] 输出 1 -1 -1；n=0 只输出空行。

数据范围与限制

• 0 <= n <= 200000；当 n=0 时第二行为空，输出空行。
• 输入规模不超过 200000，除题面另有说明外整数使用 64 位有符号范围。
• 标准输出只保留题目要求的结果；调试信息写入标准错误。
• 目标算法应为线性或摊还线性时间，辅助空间不超过 O(n)。

边界与验收重点

• 全递减、全递增、等高平台及负数。
• 等于栈顶的值不能触发“严格更小”的结算。
• 未找到答案的下标保持 -1；n=0 输出空行。

如何验证

make doctor
make run
make score

未安装 Make 时，在仓库根目录运行：

pnpm lab:validate -- labs/chapter-02/exercise/E-02-13-next-smaller-element
pnpm lab:run -- labs/chapter-02/exercise/E-02-13-next-smaller-element
pnpm lab:score -- labs/chapter-02/exercise/E-02-13-next-smaller-element

• 全部 20 个公开测试通过。
• 能手算 [2,1,2] 与 [2,2]。
• 能说明时间 O(n)、额外空间 O(n)。

思考与复盘

1. 为什么比较条件必须是 <，不能是 <=？
2. 为什么扫描结束后栈中剩余位置的答案均为 -1？

思考题参考

1. 相等不是严格更小；[2,2] 没有满足条件的右侧元素。
2. 扫描过全部右侧元素后仍未触发出栈，说明不存在严格更小值。

题解

点击查看题解

思路与不变量

从左到右维护等待答案的下标栈，使栈内对应值单调不减。当前值 a[i] 到来时，栈顶值严格大于当前值的位置，其右侧第一个严格更小值就是 a[i]，可以立即结算。

算法步骤

1. 将答案数组初始化为 -1；
2. 扫描每个位置，弹出所有满足 a[stack.top()] > a[i] 的下标并写入当前值；
3. 将当前位置压栈；
4. 扫描结束后，栈中剩余位置没有严格更小值，继续保持 -1。

正确性说明

下标只有在遇到第一个严格更小的当前值时才会出栈；在此之前扫描过的右侧元素都不满足条件，因此当前值确实是最靠左的合法答案。相等值不触发结算，保证“严格更小”的定义。

复杂度分析

• 时间复杂度：O(n)，每个位置最多入栈、出栈一次；
• 额外空间：O(n)。

边界注意

• 比较条件必须是 >，不能把相等值当成更小值；
• 全递增、单元素和 n=0 都应正确处理；
• 结果顺序仍按原下标输出，而不是按栈弹出顺序输出。