题解 | #枪打出头鸟#

思路：

题目的主要信息：

n个人的身高用数组a表示
每个人往前面开枪，会打到他前面比他高的第一个人，同时荒唐度增加被打到这个人的次序号（下标+1）
求最后总的荒唐度
方法一：暴力解法*

具体做法：*
遍历数组每个人，然后每次往这个前面找到第一个大于它的元素，返回值增加下标加1.

class Solution {
public:
   long long solve(int n, vector<int>& a) {
       long long res = 0;
       for(int i = 1; i < n; i++){
           int j = i - 1; //往前
           while(j >= 0 && a[j] <= a[i]) //往前找到第一个大于i的j
               j--;
           res += j + 1; //下标数加1
       }
       return res;
   }
};

复杂度分析：

时间复杂度： $O(n^2)$ ，最坏情况的是第一个元素最大，后续是递增序列，需要循环两层
空间复杂度： $O(1)$ ，常数级变量空间

方法二：单调栈
具体做法：
使用一个栈保存一个从栈底到栈顶的单调递减序列，同时记录其次序号。遍历的时候需要从a[i]左边找到第一个大于它的元素，我们就可以不断从栈中弹出小于它的然后将其加入栈，因为比它小的都会被它挡住，在后续相当于没用了。
图片说明

class Solution {
public:
    long long solve(int n, vector<int>& a) {
        long long res = 0;
        stack<pair<int, int> > s; //分别记录身高和次序号（下标+1）
        s.push({a[0], 1});
        for(int i = 0; i < n; i++){
            while(!s.empty() && s.top().first <= a[i]) //往前找到第一个大于a[i]的
                s.pop();
            if(!s.empty()) //不为空说明有打到人
                res += s.top().second;
            s.push({a[i], i + 1});
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，外循环为 $O(n)$ ，内循环在整个外循环过程中总共访问次数不可能超过数组中长度 $n$ ，故总计最多访问为 $2n$ 次
空间复杂度： $O(n)$ ，栈空间最大为 $n$