[USACO06NOV] Bad Hair Day S

GitHub跳转原题关系图返回列表

从左到右维护严格递减高度栈，当前入场前仍在栈中的牛都能看到它。

OJ: luogu

题目 ID: P2866

难度:普及

标签:单调栈栈USACOpython

创建: 2026-06-18 16:33

更新: 2026-10-07 10:45

后置题目
roj 3048「City Game」 城市游戏B 复用 A 教的『新元素到来先弹出违反单调性的栈顶』这一单调栈维护动作，把它从统计可见牛数迁移为直方图扫描时弹栈夹出左右边界结算面积。roj 3032「Largest Rectangle in a Histogram」 直方图中最大的矩形B 的直方图单调栈复用 A 教的具体弹栈判定：扫描到 i 时若 h_i <= h_top 就弹出栈顶（与 A「弹出所有 <=current 的栈顶」同一比较），只是把 A 弹栈后累加 len(stack) 换成用新栈顶和 i 结算 h_top×(i-L-1)；在此之上再叠加「最优矩形高等于某根柱子」的转化、边界 L/R 公式与末尾哨兵 0 这些 A 未教的新流程。roj 10003牛牛的滑动窗口A 教的「弹出所有 `<=` 当前值的栈顶、保留严格递减的高度栈」正是 B 的 max 栈实际使用的同一步（弹出条件 top<=x 收集左移时的记录值位置），B 在其上再叠加 min 栈、按下标归并分段与差分入账。luogu P7167[eJOI 2020] Fountain (Day1)B 沿用 A 的单调栈弹出所有不超过当前者、栈顶即第一个更高位置这一机制求溢出去向 nxt[i]，再叠加倍增链上跳跃shumeng CSP201312C最大的矩形B 的最大矩形复用 A 教的「单调栈弹出维护、弹出即结算」这一步（弹后新栈顶给出左界、当前 i 给出右界），再叠加同高旧柱继承扩展范围的处理与末尾 0 哨兵清栈。

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

每头牛能看到右侧连续比自己矮的牛，直到遇到第一头不矮于自己的牛。求所有可见数量之和。

思路

从左到右加入当前牛。栈中保存还没有被更高或等高牛挡住的历史高度，并保持严格递减。

当前高度到来时，先弹出所有 <= current 的栈顶：这些牛会被当前牛挡住，也不能看到当前牛。剩余栈里的每头牛都比当前牛高且中间没有遮挡，因此答案增加 len(stack)，再压入当前高度。

Python 知识

  • Python 列表尾部 append/pop 就是高效栈。
  • 只保存高度，不需要保存下标或完整序列。
  • answer += len(stack) 一次统计所有能看到当前牛的历史牛。

代码

python
import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
_ = next(data)
stack = []
answer = 0
for height in data:
    while stack and stack[-1] <= height:
        stack.pop()
    answer += len(stack)
    stack.append(height)
print(answer)

复杂度

时间复杂度 O(n)O(n)，空间复杂度 O(n)O(n)。

总结

单调栈保留“仍可能继续向右看”的牛，每头牛最多入栈、出栈一次。