题解

第一种解法：我直接从右到左一轮一轮模拟可不可以？
当然是不可以的，有一种数据会直接卡死你，n,1,2,3,4,5,6,7,8....n-1。
时间复杂度直接变成

正确解法：
单调栈
我们发现一轮一轮扫，我们浪费了很多次已知的信息。
我们研究一下规律可以发现：
对于一条鱼而言，只会被左边的鱼吃掉。
那么它被吃的时间是不是应该是
左边比自己小的鱼的集合里面 被吃时间最大的+1
那么我们就可以考虑去维护一个单调递增的栈，去求每条鱼被吃的时间
那么所有鱼被吃时间最大的那个就是我们的鱼的总数不会变的答案

时间复杂度O(n)
空间复杂度O(n)

代码

class Solution {
public:
    /**
     *
     * @param N int整型 N条鱼
     * @param A int整型vector 每条鱼的体积为Ai
     * @return int整型

    int solve(int N, vector<int>& A) {
        // write code here
        int f[100005];
        stack<int>s;
        int ans=0;
        for (int i=0; i<N; i++)
        {
            int maxn=0;
            if (s.size()==0)
            {
                s.push(A[i]); continue;
            }
            while (s.size()!=0 && s.top()<A[i])
            {
                maxn=max(maxn,f[s.top()]);
                s.pop();
            }
            s.push(A[i]);
            if (s.size()==1) continue;

            f[A[i]]=maxn+1;
            ans=max(ans,f[A[i]]);
        }
        return ans;
   }
};