题解 | #枪打出头鸟#

观察题目发现一个特性：能否射到前面的人，是从后往前看的，也就是逆序的观察数组数据，这是不是很像栈的特性？

• 于是我们建立一个辅助栈，并从后往前的遍历数组。
  • 如果栈不为空而且当前遍历元素大于栈顶元素，此时发生射击事件。那么循环将栈顶元素出栈同时累加被射击者位置，直到不满足循环条件，即射击事件不再发生
  • 当栈空或者当前遍历元素小于等于栈顶元素时，不发生射击事件，将当前元素放入栈中

    import java.util.*;
    public class Solution {
     /**
      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
      *
      * 
      * @param n int整型 n个人
      * @param a int整型一维数组 ai代表第i个人的高度
      * @return long长整型
      */
     public long solve (int n, int[] a) {
         // write code here
         long sum = 0;
         Stack<Integer> stack = new Stack<>();
         for(int cur = n-1; cur >= 0 ;cur--){
             while(stack.size() > 0 && a[cur] > stack.peek()){
               sum = sum+cur+1;
               stack.pop();
             }
             stack.push(a[cur]);
         }
         return (long)sum;
     }
    }