描述

这是一篇面对初级coder的题解。
知识点：栈
难度：三星

---

题解

现在有n个人站成一列，第i个人的身高为 第i个人射击的水弹，就会击中在他前面第一个比他高的人。
对于第i个人，如果他击中了第j个人，则荒唐度加j，如果没有击中任何人，则荒唐度加0,求荒唐度

分析
本题最为简单想到的方式是暴力解法 双重遍历
但能否对结果做优化 避免重复遍历

方法一：暴力求解

双重遍历

class Solution {
public:
    long long solve(int n, vector<int>& a) {
        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;//记录位置（从1开始要+1）
                    break;//跳出循环
                }
            }
        }
        return ans;
    }
};

复杂度分析：
循环遍历两轮,最坏情况下,时间复杂度为
由于使用的额外的空间为常数（ans ，i，j），空间复杂度为
运行测试：
运行时间 96ms 占用内存 16112KB

方法二：

由于高的人会挡住低的人
故用一个栈来记录当前可以打到人的状态

class Solution {
public:
    long long solve(int n, vector<int>& a) {
        long long ans=0;//返回值
        stack<int> s;
        for(int i=0;i<n;i++){//遍历每个元素
            while(!s.empty()&&a[i]>=a[s.top()])
                s.pop();//将能被当住的点都出栈
            if(!s.empty()) //栈不为空说明有打到人
                ans += s.top()+1;//记录位置（从1开始要+1）
            s.push(i);//元素入栈
        }
        return ans;
    }
};

注意到 虽然此时时间复杂度优化了，但是时间反而变长了，其本质原因是因为stack频繁申请释放内存耗费大量CPU时间
故自己实现栈 预先申请空间，用时有明显优化

class Solution {
public:
    long long solve(int n, vector<int>& a) {
        long long ans=0;//返回值
        vector<int> mystack(n);
        int top=0;
        for(int i=0;i<n;i++){//遍历每个元素
            while(top!=0&&a[i]>=a[mystack[top]])
                top--;//将能被当住的点都出栈
            if(top!=0) //栈不为空说明有打到人
                ans += mystack[top]+1;//记录位置（从1开始要+1）
            mystack[++top]=i;//元素入栈
        }
        return ans;
    }
};

复杂度分析：
循环遍历两遍,时间复杂度为
最坏情况下，栈会存储所有的元素，空间复杂度为

总结

对于规律性的最大最小值，可以用栈的形式进行存储和处理
用栈存储的本质是空间换时间，
当数据量较小的时候，时间复杂度小的方法可能因为操作复杂导致用时大于时间复杂度大的方法