题解 | #大鱼吃小鱼#

思路：

题目的主要信息：

• 数组A表示N条鱼各自的大小，对于每条鱼，它在每一次操作时会吃掉右边比自己小的第一条鱼
• 吃的操作是同时，即如果有一连串递减子序列，只会剩下子序列最左边的元素
• 问要多少次操作，鱼的数量就不会变了

方法一：暴力模拟法
具体做法：
我们可以模拟这个吃的过程。首先按照上面说到的每次第一条鱼不会被吃，会被留下来，后续的鱼如果左边的鱼小于右边的鱼，右边的鱼才可以留下来，将留下来的鱼都按照顺序加入一个新的数组，然后将原数组更新为新数组，继续进行这样的操作，直到新旧数组的元素个数相等，即代表一次操作没有任何的吃掉行为，可以结束。

class Solution {
public:
    int solve(int N, vector<int>& A) {
        vector<int> B;
        int res = 0;
        bool flag = true; //记录是否不能再吞并
        while(flag){
            for(int i = 0; i < A.size() - 1; i++){
                if(i == 0)
                    B.push_back(A[0]); //初始值不能被吞
                if(A[i] <= A[i + 1])  //后续小的在前不能被吞
                    B.push_back(A[i + 1]);
            }
            if(A.size() != B.size()){ //还可以继续吞
                res++;
                while(!A.empty())
                    A.pop_back();
                A = B;
                while(!B.empty())
                    B.pop_back();
            }
            if(A.size() == B.size() || A.size() == 1 || B.size() == 1) //不能继续吞了
                flag = false;
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，最坏情况需要吞并次，每次循环中都要次
• 空间复杂度：，辅助数组B的最大长度

方法二：栈
具体做法：
用结构表示大鱼的大小即到此处的吞并次数。我们从A数组的尾到首部，每次遇到一条鱼就都要将其入栈，栈内是该数及到该数可以吞并的次数，同时我们也要比较栈中元素和该数的大小，不断弹出栈中较小的元素，累计吞并次数。

class Solution {
public:
    struct node{
        int x, time; //数组和吞并次数
    };
    int solve(int N, vector<int>& A) {
        stack<node> s;
        int res = 0;
        for(int i = N - 1; i >= 0; i--){ //从尾到头
            int time = 0;
            while(!s.empty() && A[i] > s.top().x){
                time = max(s.top().time, time + 1);  //吞并次数叠加
                s.pop();
            }
            s.push({A[i], time}); //入栈
            res = max(res, time);
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，一次到的外循环遍历，中间的while循环累计起来才会遍历个数，所以相当于是
• 空间复杂度：，栈空间最大为N