题解 | #枪打出头鸟#

题目关键信息：
有n个数，向左寻找第一个当前值大的第一个数，求它们所处位置的累加和
方法一：单调栈
定义一个类P可以存储元素的值和位置，将n个元素包装为类P入栈，如果栈非空并且当前元素值大于栈顶元素值时不断将栈中的元素出栈，直到找到第一个比当前元素值大的元素，将找到的元素索引累加得到结果

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n个人
     * @param a int整型一维数组 ai代表第i个人的高度
     * @return long长整型
     */
    class P{
        int val,index;
        P(int val,int index){
            this.val=val;//值
            this.index=index;//索引
        }
    }
    public long solve (int n, int[] a) {
        // write code here
        Stack<P>s=new Stack<P>();
        long res=0;
        for(int i=0;i<a.length;i++){
            while(!s.isEmpty()&&s.peek().val<=a[i]){s.pop();}//弹出栈中所有比当前值小的元素
            if(!s.isEmpty())res+=s.peek().index;//直到栈中元素比当前元素大，即当前元素向左找到第一个比它大的元
            s.push(new P(a[i],i+1));
        }return res;
    }
}

复杂度：
时间复杂度：每个元素最多出栈入栈一次
空间复杂度：,栈的大小不超过n

方法二：暴力查找
设置一个指针指向当前元素的前一个元素，不断向前查找找到第一个比当前值大的元素，更新结果

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 res=0;
        for(int i=1;i<a.length;i++){
            int l=i-1;//指向当前值的前一位
            while(l>=0&&a[l]<=a[i])l--;//不断向前查找直到找到第一个比当前值大的数
            res+=(l+1);
        }return res;
    }
}

复杂度：
时间复杂度： ,双层循环
空间复杂度:,只使用了临时的辅助变量