题解 | #愤怒的小鸟#

#include <bits/stdc++.h> 

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> arr(n);
    
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    
    vector<int> l(n),r(n); // l[i] 第i个山丘的左边比他高的山丘的数量！r[i] 右边比他高的山丘的数量！
    
    stack<int> stk;
    
    
    for(int i = 0; i < n; i++){
        while(!stk.empty() && arr[stk.top()] < arr[i]) stk.pop();
        l[i] = stk.size();
        stk.push(i);
    }
    
    stack<int>().swap(stk); // 没有clear方法就这样吧！
    
    for(int i = n-1; i >= 0; i--){
        while(!stk.empty() && arr[stk.top()] < arr[i]) stk.pop();
        r[i] = stk.size();
        stk.push(i);
    }
    
    for(int i = 0; i < n; i++){
        cout << (n - 1 - l[i]-r[i])<< " ";
    }
    return 0;
    
}