POJ 3250 Bad Hair Day：單調棧計算每頭牛能看到的牛數

題目大意

N 頭牛排成一排（N≤50000），每頭牛有高度 h[i]。牛 i 向右看，能看到多少頭牛？只能看到比自己矮的，遇到 ≥ 自身高度的牛視線被擋住。求所有牛看到的牛數之和。

單調棧核心思想

維護一個單調遞減棧（棧底到棧頂高度遞減）。從右向左遍歷：

• 當前牛 i，高度 h[i]
• 彈出棧頂所有 h[top] < h[i] 的牛（它們被 i 看見，且不再被更左的牛看見）
• 彈出次數 = 牛 i 能看到的牛數
• 將 i 入棧

為什麼正確？

• 棧中始終保存「尚未被更左的牛看見」的牛
• 高度遞減保證：若 h[j] < h[i] 且 在 i 右側，則 i 一定能看見 j（中間沒有更高的擋住）
• 彈出後 j 不會再被更左的牛看見，因為 i 已經擋住視線

完整代碼

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> h(N);
    for (int i=0;i> h[i];
    
    vector<int> stk; stk.reserve(N);
    ll ans = 0;
    for (int i=N-1; i>=0; --i) {
        int cnt = 0;
        while (!stk.empty() && h[stk.back()] < h[i]) {
            stk.pop_back();
            cnt++;
        }
        ans += cnt;
        stk.push_back(i);
    }
    cout << ans << "\n";
    return 0;
}

變體：非嚴格單調（≤ 或 ≥）

• 題目說「遇到 ≥ 自身高度視線被擋住」 → 嚴格遞減棧（h[top] < h[i] 彈出）
• 若「> 擋住」 → 單調非遞增棧（h[top] ≤ h[i] 彈出）

複雜度

• 每頭牛最多入棧、出棧各一次 → O(N) 時間
• 棧空間 O(N)

單調棧經典應用總結