POJ 3250 Bad Hair Day：單調棧統計可見牛數

題目

N 頭牛 (N≤80,000) 面向東站成一排，高度 h_i。牛 i 能看到其右側比它矮的牛，直到遇到 ≥ h_i 的牛為止。求所有牛能看到的牛數之和。

單調棧解法

維護一個單調遞減棧（棧底到棧頂高度遞減）。遍歷牛：
1. 當棧不為空且棧頂高度 ≤ 當前高度 → 彈出（這些牛被當前牛擋住，不可見）。
2. 此時棧中剩余牛的個數 = 能看到當前牛的牛數（它們比當前牛高且中間無更高牛）。累加到答案。
3. 將當前牛入棧。
每頭牛進棧出棧各一次，O(N) 時間。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; 
    while (scanf("%d", &n) == 1) {
        long long ans = 0;
        stack st;
        for (int i = 0; i < n; i++) {
            int h; scanf("%d", &h);
            while (!st.empty() && st.top() <= h) st.pop();
            ans += st.size();
            st.push(h);
        }
        printf("%lld\n", ans);
    }
    return 0;
}