题意分析

给出一个序列，需要找到每个位置的数字前面的比他大的第一个数字的位置。将这个下标累加到最后的答案里面。

思路分析

思路一暴力查找

既然是找每个位置的前面比它打的第一个数字，那么我们直接用暴力查找就行了。枚举每个位置，然后从这个位置的前面查找比这个位置的数字大的第一个位置。
代码如下
- 双重循环遍历这个序列。时间复杂度为 $O (n^{2})$
- 只开了少数几个变量，空间复杂度为 $O (1)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n个人
     * @param a int整型vector ai代表第i个人的高度
     * @return long长整型
     */
    long long solve(int n, vector<int>& a) {
        // write code here
        long long ans=0;
        // 枚举每个位置
        for(int i=0;i<n;i++){
            // 从这个位置之前找到第一个大于这个位置的数字，然退出
            for(int j=i-1;j>=0;j--){
                if(a[j]>a[i]){
                    ans+=(j+1);
                    break;
                }
            }
        }
        
        return ans;
    }
};

思路二单调栈

这个题目是单调栈的模板题。我们需要找到每个位置的前面第一个比他大的，其实和栈的后进先出的模型很匹配。后进先出就相当与前面最接近当前位置的满足条件的数字。这里我们根据需求使用一个单调递减栈来进行操作。
如下图

图片说明

我们看到这个图解，先进入栈里面的元素反倒是在栈的底部，后进的反倒是在栈的顶部，这个不正符合我们这个题目的意思吗？顶部就相当与是更加接近我们当前要求的这个数字。顶部符合的话就是我们要找的了。不符合那么就一直出栈知道满足。
有了单调栈的思想，我们就可以很好地解决这个题目了。只是在这个题目为了记录下标，我们需要使用一个结构体存储每个元素。
- 如果栈是空的，那么直接元素进栈。
- 如果栈是非空的，那么一直查询栈定第一个数字的大小进行比较，小的话那么就出栈，下一个栈顶继续判断。如此循环。
代码如下
- 利用单调栈解决，直接扫一遍就行了，时间复杂度为 $O (n)$
- 在过程中利用了栈存储元素，最多可能存储 $n$ 个元素，空间复杂度为 $O (n)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n个人
     * @param a int整型vector ai代表第i个人的高度
     * @return long长整型
     */
    // 定义一个结构体，记录下标和数字
    struct node{
        int idx;
        int num;
    };
    stack<node> st;
    long long solve(int n, vector<int>& a) {
        // write code here
        long long ans=0;
        
        
        for(int i=0;i<n;i++){
            // 如果栈是空的，那么直接放入
            if(st.empty()){
                st.push({i+1,a[i]});
            }else{
                // 如果不是空的，那么找到栈顶第一个比它大的元素
                while(!st.empty()){
                    if(st.top().num>a[i]){
                        ans+=st.top().idx;
                        break;
                    }else{
                        st.pop();
                    }
                }
                // 将这个位置的数字放入
                st.push({i+1,a[i]});
            }
        }
        
        return ans;
    }
};

NC580 题解 | #枪打出头鸟#

题意分析

思路分析

思路一 暴力查找

思路二 单调栈

思路一暴力查找

思路二单调栈