枪打出头鸟

public class Solution {
    /**
     * 
     * @param n int整型 n个人
     * @param a int整型一维数组 ai代表第i个人的高度
     * @return long长整型
     * 用栈，随指针i，只存降序数列(包括指针)，降序存，升序出
     * 例如：1254312312
     *   i: 0123456789
     * 1，2，5，54，543，5431，5432，543，5431，5432
     * 0，1，2，3 ，4  ，5   ，6   ，7  ，8   ，9
     */
    public long solve (int n, int[] a) {
        // write code here
        if(n<=1) {
            return 0;
        }
        if(n==2) {
            return a[0]>a[1] ? 1 : 0;
        }
        List<Integer> stack = new ArrayList<>();
        long j=0;
        for(int i=0; i<n; i++) {
            while(!stack.isEmpty() && a[i]>=a[stack.get(stack.size()-1)]) {
                stack.remove(stack.size()-1);
            }
            if(!stack.isEmpty()) {
                j+=stack.get(stack.size()-1)+1;
            }
            stack.add(i);
        }
        return j;
    }
}

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 ht=0;
        int[] hts=new int[n];
        int pre=0,ppre=0;
        if(n<=1){
            return 0;
        }
        if(a[0]>a[1]){
            ht=1;
            hts[1]=1;
        }
        if(n==2){
            return ht;
        }
        pre=1;
        ppre=hts[pre-1];
        for(int i=2;i<n;i++){
            if(a[i]<a[i-1]){
                hts[i]=i;
            }else{
                pre=i-1;
                while(a[i]>=a[pre]&&(ppre=hts[pre])!=0){
                    if(a[i]<a[ppre-1]){
                        hts[i]=ppre;
                        break;
                    }else{
                        pre=ppre-1;
                    }
                }
            }
            ht+=hts[i];
        }
        return ht;
    }
}