题解 | #枪打出头鸟#

题意整理

n个人站成一列，如果某个人的前面有身高比他高的，则第一个比他高的会中枪。
只要某个人中枪了，则荒唐度会增加对应那个人的编号，求最终的荒唐度。

方法一（暴力法）

1.解题思路

直接遍历所有的人，内层循环中找到第一个比他高的人，加上对应编号，如果找到，立即终止内层循环。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n个人
     * @param a int整型一维数组 ai代表第i个人的高度
     * @return long长整型
     */
    public long solve (int n, int[] a) {
        //初始化结果变量
        long res=0;

        //循环遍历数组
        for(int i=1;i<n;i++){
            //找到第一个大于当前身高的人
            for(int j=i-1;j>=0;j--){
                if(a[j]>a[i]){
                    res+=j+1;
                    break;
                }
            }
        }

        return res;
    }
}

3.复杂度分析

时间复杂度：最坏情况下，总是第一个人中枪，需要遍历 $图片说明$ 次，所以时间复杂度是 $O(n^2)$ 。
空间复杂度：不需要额外的内存空间，所以空间复杂度是 $O(1)$ 。

方法二（单调栈）

1.解题思路

初始化一个单调栈，顺序存储所有人的编号。
只要栈顶对应的那个人身高小于当前身高，说明不会被打中，直接从栈中移除。这个过程结束后，如果栈中还有人，则一定是第一个大于当前身高的人，加上对应荒唐度，继续下一轮循环。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n个人
     * @param a int整型一维数组 ai代表第i个人的高度
     * @return long长整型
     */
    public long solve (int n, int[] a) {
        //初始化结果变量
        long res=0;

        //初始化单调栈
        LinkedList<Integer> stack=new LinkedList<>();
        for(int i=0;i<n;i++){
            //只要栈顶身高小于当前身高，就从栈中移除
            while(!stack.isEmpty()&&a[stack.peek()-1]<=a[i]){
                stack.pop();
            }
            //如果栈中还有元素，则栈顶一定是第一个身高大于当前元素的
            if(!stack.isEmpty()){
                res+=stack.peek();
            }
            //将每一个人的编号入栈
            stack.push(i+1);
        }

        return res;
    }
}

3.复杂度分析

时间复杂度：每个人最多入栈和出栈一次，所以时间复杂度是 $O(n)$ 。
空间复杂度：需要额外大小为n的栈，所以空间复杂度是 $O(n)$ 。