POJ 3250 Bad Hair Day 單調棧 可見牛對數

等價轉化

對每頭牛 i，計算其右側連續比它矮的牛數量，直到遇到第一頭 ≥ h[i] 的牛。即「下一個更大或等元素」之前的元素個數。

單調棧 O(N) 解法

從右向左掃描，維护嚴格遞減棧（棧頂到棧底高度遞增）。

演算法流程

1. 初始化空棧，存儲下標
2. 對 i 從 N-1 降到 0：
   • 當棧不為空且 h[stack.top()] < h[i]，彈出（這些牛被 i 遮擋）
   • 當前牛能看到的牛數 = stack.empty() ? (N-1-i) : (stack.top() - i - 1)
   • 將 i 入棧
3. 累加所有牛的可見數

代碼實現

#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int N; scanf("%d", &N);
    vector<long long> h(N);
    for (int i = 0; i < N; ++i) scanf("%lld", &h[i]);

    vector<int> st;
    long long ans = 0;
    for (int i = N-1; i >= 0; --i) {
        while (!st.empty() && h[st.back()] < h[i]) st.pop_back();
        int see = st.empty() ? (N-1-i) : (st.back() - i - 1);
        ans += see;
        st.push_back(i);
    }
    printf("%lld\n", ans);
    return 0;
}

樣例驗證

高度: 10 3 7 4 12 2
i=5 (2): 見 0, 棧=[5]
i=4 (12): 彈 5, 見 1, 棧=[4]
i=3 (4): 見 0, 棧=[4,3]
i=2 (7): 彈 3, 見 1, 棧=[4,2]
i=1 (3): 見 0, 棧=[4,2,1]
i=0 (10): 彈 1,2, 見 3, 棧=[4,0]
總計: 0+1+0+1+0+3 = 5 ✓

關鍵點

• 嚴格遞減棧：相同高度不彈出（題目要求「嚴格矮」）
• 從右向左掃描，棧中保存「未被遮擋」的牛
• 長整型防溢出（N=8e4 時最大對數 ~3.2e9）