题解 | #大鱼吃小鱼#

一.题目描述
题目大意：有一个N个数的数列，每一个数可以删去右边连续递减且小于当前数的数列，返回需要进行几次操作可以使得数列保持稳定，其数量不会发生变化。
图片说明
二.算法(模拟+递归)
理解题目的意思我们可以知道每次都会将一个数右边小于该数字的连续子序列删除，那么对于每次删除后的结果进行递归，记录最后数列趋于稳定所需要的次数，返回就可以得到最后的答案了，下面是完整代码和注释：

class Solution {
public:
    /*
    不是吧 不是吧 不会有人还 不知道 这个题目的数据弱的只有一个数据点吧 22
    */
    int solve(int N, vector<int>& A) {
        vector<int>num;//需要一个额外的数组来记录进行删除处理后的数组
        for(int i=N-1;i>=1;i--){
            if(A[i]>A[i-1]){
                //每次只记录大的那个数字，小数字是会被删除的
                num.push_back(A[i]);
            }
        }
        num.push_back(A[0]);//第一个数字需要做特殊处理放进去
        //对数组进行翻转
        reverse(num.begin(),num.end());
        //表示数组的状态趋于稳定，数量不会发生变化
        if(num.size()==N){
            return 0;
        }
        //每次操作的数量都进行加一的计数操作
        return solve(num.size(),num)+1;
    }
};

时间复杂度： $O(n^{2})$ 最坏需要进行n次操作
空间复杂度： $O(n)$ 需要开辟空间来储存操作过后的数组
三.算法(bfs)
图片说明（图片来自牛客）
利用结构体建立一个节点栈，每个结点记录每一个数的大小和每一个数可以删除右边数的次数，如果当前的结点的数值大于栈顶结点的数值，那么将栈顶的结点出栈，并且维护当前结点可以删除右边数的次数最大值，当栈顶结点的数值大于当当前结点的大小或者栈空时，当前结点进栈的时候，维护删除的最大值，返回最后返回的最大值即可，下面是完整代码和注释：

class Solution {
public:
    //每一个结点的值和最大删除次数
    struct node{
        int num;
        int cnt;
    };
    int ans=0;//需要维护的最大值
    void bfs(int N,vector<int>& A){
        stack<node>st;
        for(int i=N-1;i>=0;i--){
            int mx=0;
            //栈不是空的时候并且当前结点的值大于栈顶结点的值
            while(st.size()&&A[i]>st.top().num){
                    mx=max(mx+1,st.top().cnt);
                    st.pop();
            }
            //将新的结点入栈
            st.push({A[i],mx});
            //维护最大的值
            ans=max(ans,mx);
        }
    }
    int solve(int N, vector<int>& A) {
        bfs(N,A);
        return ans;
    }
};

时间复杂度： $O(n^{2})$ 最坏需要进行n次操作
空间复杂度： $O(n)$ 需要用栈来存储