题解 | #大鱼吃小鱼#

题目：
现在有N条鱼，每条鱼的体积为Ai，从左到右拍成一排。
A数组是一个排列。
牛牛每轮可以执行一次大鱼吃小鱼的操作
一次大鱼吃小鱼的操作：对于每条鱼，它在每一次操作时会吃掉右边比自己小的第一条鱼
值得注意的时，在一次操作中，每条鱼吃比自己小的鱼的时候是同时发生的。
举一个例子，假设现在有三条鱼,体积为分别[5，4，3]，5吃4，4吃3，一次操作后就剩下[5]一条鱼。
牛爸问牛牛，你知道要多少次操作，鱼的数量就不会变了嘛？
输出：表示要多少次操作，鱼的数量就不会变了
方法一：利用栈
构造一个表示鱼的类，类中包含鱼的体积x和鱼可以吃到的鱼的最大数量nums

定义一个栈记录鱼的生存情况，从后往前遍历数组，让鱼进栈
如果当前鱼的体积大于栈顶鱼的体积，当前鱼可以吃掉栈顶的鱼（出栈），并且更新当前鱼可以吃到的鱼的数量最大值，直到栈顶鱼的体积大于当前鱼的体积或者栈空时，当前鱼进栈，维护可以吃鱼的最大数量
继续让鱼进栈，重复步骤一二

图片说明
Java版本

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param N int整型 N条鱼
     * @param A int整型一维数组 每条鱼的体积为Ai
     * @return int整型
     */
    class Fish{
        int x,nums;
        Fish(int x,int nums){
            this.x=x;//鱼的体积大小
            this.nums=nums;//鱼可以吃到的鱼的数量
        }
    }
    public int solve (int N, int[] A) {
        // write code here
        Stack<Fish>s=new Stack<Fish>();
        int count=0;
        for(int i=N-1;i>=0;i--){
            int nums=0;
            while(!s.isEmpty()&&A[i]>s.peek().x){//栈非空并且当前鱼的体积大于栈顶鱼的体积时
                nums=Math.max(s.peek().nums,nums+1);//更新最大值
                s.pop();//被吃掉的鱼出栈
            }
            s.push(new Fish(A[i],nums));
            count=Math.max(count,nums);//选出那条可以吃鱼最多的鱼，返回它能吃到的鱼的数量
        }
        return count;
    }
}

复杂度：
时间复杂度：每个元素最多进栈一次，平均时间复杂度为 $O(N)$ ,
空间复杂度：栈的大小不超过N， $O(N)$
方法二：递归
从后往前让每一个连续递减子段的最大值加入新数组arr，arr需要逆置,再继续递归
递归终止条件为数组大小小于等于1或者存储递减子段最大值的数组大小不变，直接返回0
图片说明
C++版本

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param N int整型 N条鱼
     * @param A int整型vector 每条鱼的体积为Ai
     * @return int整型
     */
    int solve(int N, vector<int>& A) {
        // write code here
        vector<int>arr;
        for(int i=A.size()-1;i>=1;i--){
            if(A[i]<A[i-1])continue;
            arr.push_back(A[i]);//将每一个连续递减子段的最大值加入arr
        }arr.push_back(A[0]);
        reverse(arr.begin(),arr.end());//顺序反转
        if(A.size()<=1||arr.size()==N)return 0;//递归终止条件：如果新数组大小不变或者数组大小小于等于1直接返回0
        return 1+solve(arr.size(),arr);
    }
};

复杂度：
时间复杂度：每次递归复杂度 $O(N)$ ,递归次数不超过N,因此时间复杂度为 $图片说明$
空间复杂度：递归运行时栈大小不超过N， $O(N)$