题解 | #愤怒的小鸟#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int h[]=new int[n];
        for(int i=0;i<n;i++){
            h[i]=in.nextInt();
        }
        Stack<Integer> stack=new Stack<>();
        stack.push(0);
        int res[]=new int[n];
        //从左到右找能炸自己的山的数量
        for(int i=1;i<n;i++){
            while(!stack.isEmpty()&&h[i]>h[stack.peek()]){
                stack.pop();
            }
            if(!stack.isEmpty())
                res[i]+=stack.size();
            stack.push(i);
        }
        //从右到左找能炸自己的山的数量
        stack.clear();
        stack.push(n-1);
        for(int i=n-2;i>=0;i--){
            while(!stack.isEmpty()&&h[i]>h[stack.peek()]){
                stack.pop();
            }
            if(!stack.isEmpty())
                res[i]+=stack.size();
            stack.push(i);
        }
        for(int i=0;i<n;i++){
            res[i]=n-1-res[i];
        }
        for(int i=0;i<n;i++){
            System.out.print(res[i]+" ");
        }

    }
}

不要正向找安全点，先找非安全点，然后用n-1减去非安全点数。

开始想的是找安全点，结果写到后面发现需要考虑好多好多情况……属实想不全所有情况，所以反向考虑了。