Java Program to Find How Many Fish (N Voracious Fish) Are Alive Moving Along a River | Codility Fish Solution

问题陈述

N 条贪食的鱼沿着河流游动。 每条鱼都有一个体重和一个前进方向。代表河流的一维数组中的每个元素都是一条鱼。鱼可能逆流而上或顺流而下。较大的鱼会吞食较小的鱼，如果它们接触到的话。我们的目标是找出所有潜在的互动后有多少条鱼能够存活。

输入

• A[]： 一个整数 数组，其中每个元素代表一条鱼的大小。大小是一个正整数。
• B[]： 一个整数数组，其中每个元素代表一条鱼的移动方向
  
  • 0 表示鱼正在逆流而上。
  • 1 表示鱼正在顺流而下。

输出

一个整数，表示所有互动后将存活的鱼的数量。

问题分析

要解决这个问题，我们需要模拟鱼在相反方向移动时的互动。

1. 逆流而上（0）的鱼只会遇到顺流而下（1）的鱼。
2. 当一条顺流而下的鱼遇到一条逆流而上的鱼时，较小的鱼会被吃掉，较大的鱼会继续前进。
3. 沿同一方向游动的鱼永远不会相遇，因此它们会存活下来。

方法

1. 堆栈数据结构： 我们将使用堆栈来跟踪目前正在顺流而下的鱼。堆栈将存储鱼的大小。
2. 模拟河流
   
   • 遍历河流中的每一条鱼。
   • 如果鱼正在顺流而下（1），则将其大小压入 堆栈。
   • 如果鱼正在逆流而上（0），则检查堆栈。
     
     • 如果堆栈不为空，并且堆栈顶部的鱼正在顺流而下，则比较大小。
       
       • 如果堆栈中的鱼（顺流而下）更大，则当前的鱼（逆流而上）被吃掉。
       • 如果当前的鱼（逆流而上）更大，则从堆栈中弹出鱼（顺流而下的鱼被吃掉），并继续检查堆栈中的下一条鱼。
     • 如果堆栈为空，则当前的鱼正在逆流而上，没有鱼与之对抗，因此它会存活下来。
3. 计算存活的鱼
   
   • 在处理完所有逆流而上的鱼后，堆栈中仍然存在的顺流而下的鱼将存活下来。
   • 那些从未遇到过顺流而下鱼的逆流而上的鱼也会存活下来。

示例

A = [4, 3, 2, 1, 5]

B = [0, 1, 0, 0, 0]

鱼 1（大小：4，逆流而上）

鱼 2（大小：3，顺流而下）

鱼 3（大小：2，逆流而上）

鱼 4（大小：1，逆流而上）

鱼 5（大小：5，逆流而上）

解决方案

• 鱼 1 逆流而上，没有遇到任何鱼。
• 鱼 2 顺流而下，被添加到堆栈中。
• 鱼 3 逆流而上，遇到了鱼 2。
  
  • 鱼 2（大小：3）吃掉了鱼 3（大小：2）。
• 鱼 4 逆流而上，再次遇到了鱼 2。
  
  • 鱼 2（大小：3）吃掉了鱼 4（大小：1）。
• 鱼 5 逆流而上，遇到了鱼 2。
  
  • 鱼 5（大小：5）吃掉了鱼 2（大小：3）。

剩余存活的鱼是鱼 1（大小：4）和鱼 5（大小：5）。因此，输出是 2。

文件名：FishSurvival.java

输出

 
Number of fish alive: 2   

结论

这种方法使用堆栈有效地计算了所有可能互动后将存活的鱼的数量，时间复杂度为 O(N)。这种解决方案确保我们只遍历鱼一次，使其成为大型输入的最佳选择。