小明每轮可以执行一次大鱼吃小鱼的操作
一次大鱼吃小鱼的操作:对于每条鱼,它在每一次操作时会吃掉右边比自己小的第一条鱼
值得注意的是,在一次操作中,每条鱼吃比自己小的鱼的时候是同时发生的。...输入例子2:
6
4 3 2 3 2 1
输出例子2:
2
例子说明2:
[4,3,2,3,2,1]-->[4,3]-->[4]
分析
还是老套路,我们拿到题目先来分析一下题目,看看题目当中有没有遗漏或者是隐藏的一些信息...虽然题目当中说了,每条鱼会选择右侧最近的比它小的鱼进行进食,但如果它右侧的鱼比它大的话,这个食物会被抢夺。比如4,5,3,对于4来说,3是它的食物,但由于5比4大,3同样也会是5的食物。...暴力求解的最坏复杂度是 ,我们很容易举出一个例子,比如4,3,3,3,3,3,3,3。由于除了第一条鱼之外其他鱼的大小都相等,相等的鱼无法吞食。...如果当前鱼更小,无法吞吃,那么需要记录下来,因为左侧可能有更大的鱼。这样一来,我们记录数组中的鱼一定是递减的,很容易想到,这其实是一个单调栈。