Codility河中存活鱼数量计算的时间与空间复杂度问询

咱先快速捋下这个问题的核心冲突逻辑：只有当下游方向的鱼（B[P]=1）在后续遇到上游方向的鱼（B[Q]=0）时，才会发生“互吃”——大的鱼存活，小的被吃掉；同方向或者顺序不对的鱼（比如上游鱼在下游鱼前面）根本碰不到，不会有冲突。

最优解法的复杂度拆解 #

• 时间复杂度：O(N)
  最优解法是用栈来模拟整个过程：遍历每条鱼时，下游方向的鱼直接压入栈；遇到上游方向的鱼，就和栈顶的下游鱼比大小——如果当前上游鱼更大，就把栈顶的鱼弹出（意味着被吃掉），接着继续和新的栈顶比，直到栈空（这条上游鱼存活）或者栈顶的鱼更大（当前上游鱼被吃掉）。
  这里每条鱼最多只会被压入栈一次、弹出栈一次，整个遍历过程是线性的，所以时间复杂度是O(N)，这已经是理论最优了——毕竟你总得把所有鱼都过一遍吧？

• 空间复杂度：O(N)
  最坏情况是所有鱼都是下游方向（B数组全为1），这时候栈里会装下所有N条鱼，所以空间复杂度是O(N)。当然也有最好情况，比如所有鱼都是上游方向，或者一条上游鱼一路吃掉所有下游鱼，这时候栈最多只存1条鱼，空间是O(1)，但我们通常讨论的是最坏情况下的空间复杂度。

为啥这个解法是最优的？ #

因为任何解法都不可能比O(N)更快——你必须遍历每条鱼至少一次才能处理所有潜在的冲突，而栈的方式刚好做到了线性时间，没有多余的操作，空间上也没有浪费，是这个问题的最优解。

内容的提问来源于stack exchange，提问作者Nicky