学习目标

• 用单调栈确定当天左侧最近的严格更高价格。
• 正确把相等价格也计入连续跨度。
• 用下标计算跨度并证明 O(n) 时间。

前置知识与环境

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

任务

当天的价格跨度是从当天向左连续计算、价格不高于当天价格的天数，包含当天，遇到第一个严格高于当天的价格时停止。例如价格 [100,80,60,70,60,75,85] 的跨度为 [1,1,1,2,1,4,6]。

输入格式

第一行 n；第二行 n 个正整数价格。

输出格式

输出每一天的价格跨度，各数值以空格分隔，末尾换行。相等价格同样计入，例如 [3,3] 输出 1 2。

数据范围与限制

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

边界与验收重点

• 单日、严格递增、严格递减、相等平台和局部低谷。
• 栈内保存下标；等于当天价格的旧下标应弹出。
• 栈空时跨度为 i+1，否则为当前下标减去左侧最近严格更高价格的下标。

如何验证

make doctor
make run
make score

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

pnpm lab:validate -- labs/chapter-02/exercise/E-02-20-stock-span
pnpm lab:run -- labs/chapter-02/exercise/E-02-20-stock-span
pnpm lab:score -- labs/chapter-02/exercise/E-02-20-stock-span

• 全部 20 个公开测试通过。
• 能手算 [3,3] 和七日样例。
• 能证明每个下标最多入栈、出栈各一次，时间 O(n)。

思考与复盘

1. 为什么栈顶价格等于当天价格时也要弹出？
2. 栈清空时跨度为什么不是 i？

思考题参考

1. 定义包含“价格不高于当天”，相等价格不构成左边界。
2. 从下标 0 到 i 共 i+1 天，且包括当天。

题解

点击查看题解

思路与不变量

扫描价格并维护下标单调栈，栈内价格严格递减。处理第 i 天时，先弹出所有价格小于等于 price[i] 的旧下标；弹栈后栈顶就是左侧最近的严格更高价格。

算法步骤

1. 对每个下标 i，弹出所有 price[stack.top()] <= price[i] 的下标；
2. 若栈为空，跨度为 i+1，否则为 i-stack.top()；
3. 输出跨度并把 i 压栈，供后续日期使用。

正确性说明

被弹出的价格不高于当天价格，会被当天纳入连续区间，不能再作为左边界。弹栈后留下的栈顶是左侧最近的严格更高价格，区间正好从它之后到当天，因此 i-stack.top()（或栈空时的 i+1）就是最大连续跨度。

复杂度分析

• 时间复杂度：O(n)，每个下标最多入栈和出栈一次；
• 额外空间：O(n)，栈保存价格下标。

边界注意

• 相等价格必须弹出，才能把相等天数计入跨度；
• 栈为空时要加一，因为跨度包含当天和下标 0；
• 单调递减序列的跨度都是 1，单调递增序列的跨度逐步扩大。