考点：栈

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

题目画像

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

解题思路

推荐方向：栈

本题切入点

每座塔向右看到的数量 = 到「第一个严格更高的塔」之间的塔数（含该更高塔）：用单调递减栈从右往左扫即可 O(n)，等高的塔不构成阻挡需一并计入。

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

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

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

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

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

该范式的通法易错点

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

对照本题

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

样例解读

样例 1：输入 6 / 4 4 2 6 1 3 → 输出 3 2 1 2 1 0

前两座高度为 4 的塔都会被高度为 6 的塔阻挡；高度相同的塔不会提前截断视野。