题解 | #愤怒的小鸟#

• 方法：单调栈
• 思路：
• 首先找到每个点前面不能到达该点的节点数量：从前向后遍历，记录一个num表示前面所有节点中不能到达当前节点的数目,并维护一个单调递减的栈S。对于第i个节点，如果栈不为空且栈顶元素小于h[i]，则一直弹出栈顶元素，并每次把num++，因为这些元素都不能到达当前节点。然后加入当前节点到栈顶，并更新当前节点的ans：ans[i]+=num。
• 其次找到每个点后面不能到达该点的节点数量：从后往前遍历，其余同上。
• 注意：单调栈的思想，大多是不单调的节点对后面的节点「没有影响」/「等于对当前节点的影响」。比如这道题中，如果前面某些点不能到达当前节点，那么他们就一定不能达到该节点后面的点，故这些点对后面的节点「等于对当前节点的影响」

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+10;
int n;
int h[MAXN];
int ans[MAXN];
stack<int>s;
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&h[i]);
    int num = 0;
    for(int i=1;i<=n;++i){  //正向，找到每个节点前面不能到达当前节点数目
        while(!s.empty() && s.top()<h[i]){
            s.pop();
            num++;
        }
        s.push(h[i]);
        ans[i]+=num;
    }
    
    num = 0;
    while(!s.empty())s.pop();
    for(int i=n;i>=1;--i){  //逆向，找到每个节点后面不能到达当前节点数目
        while(!s.empty() && s.top()<h[i]){
            s.pop();
            num++;
        }
        s.push(h[i]);
        ans[i]+=num;
    }
    for(int i=1;i<=n;++i){
        printf("%d",ans[i]);
        i==n?printf("\n"):printf(" ");
    }
    
}
// 64 位输出请用 printf("%lld")