计算许多鱼的时间和空间复杂性还活着吗？

Question

我正在研究一个Codility问题:

您将获得两个由N个整数组成的非空零索引数组A和B. 数组A和B代表河流中的N种贪婪鱼类,沿着河流向下游排序.

鱼的编号从0到N-1.如果P和Q是两条鱼而P <Q,那么鱼P最初是鱼Q的上游.最初,每条鱼都有一个独特的位置.

鱼数P由A [P]和B [P]表示.数组A包含鱼的大小.它的所有元素都是独特的.数组B包含鱼的方向.它只包含0和/或1,其中:

0表示向上游流动的鱼,1表示向下游流动的鱼.如果两条鱼在相反的方向上移动并且它们之间没有其他(活鱼),它们最终会相遇.然后只有一条鱼可以活着 - 较大的鱼吃较小的鱼.更确切地说,当P <Q,B [P] = 1且B [Q] = 0时,我们说两条鱼P和Q彼此相遇,并且它们之间没有活鱼.他们见面后:

如果A [P]> A [Q]则P吃Q,P仍将向下游流动,如果A [Q]> A [P]则Q吃P,Q仍然会向上游流动.我们假设所有的鱼都以相同的速度流动.也就是说,沿同一方向移动的鱼永远不会相遇.目标是计算将保持活力的鱼的数量.

**Complexity:**

预期的最坏情况时间复杂度是O(N); 预期的最坏情况空间复杂度是O(N),超出输入存储(不计入输入参数所需的存储).

这是我的解决方案:( 100%正确结果)

public int solution(int[] a, int[] b) {
  int remFish = a.length; 
  int i = 0; 
  for (i = 0; i < b.length; i++) {
    if(b[i] != 0){
      /*remFish++; }else { */ break; 
    }
  } 
  Stack<Integer> myQ = new Stack<Integer>(); 
  for (int j = i; j < b.length; j++) { 
    if(b[j] == 1)
    {
      myQ.add(j); 
    } 
    while(b[j] == 0 && !myQ.isEmpty()) {
      if(a[j] > a[myQ.peek()]){ 
        myQ.pop(); remFish--; 
      }else{ 
        remFish--; 
      break; 
      }
    } 
  } 
  return remFish;
}

有人可以帮我理解我的解决方案是否超出了复杂性要求？

Answer 1

你的想法很好。我试图让它更容易理解。

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {

        int numFishes = A.length;

        // no fishes
        if(numFishes == 0)
            return 0;

        // Deque stores the fishes swimming downstreams (B[i]==1) 
        Deque<Integer> downstreams = new ArrayDeque<Integer>();

        for(int i = 0; i < A.length; i++){

            //Fish is going downstreams
            if(B[i] == 1){
                // push the fish into the Deque
                downstreams.push(A[i]); 
            }//Fish is going upstreams
            else{
                while( !downstreams.isEmpty() ){ 
                    // Downstream-fish is bigger 
                    if( downstreams.peek() > A[i] ){
                        //Upstream-fish gets eaten
                        numFishes--;
                        break;    
                    }// Downstream-fish is smaller
                    else if(downstreams.peek() < A[i]){
                        //Downstream-fish gets eaten
                        numFishes--;
                        downstreams.pop();
                    }
                }
            }  
        }    

        return numFishes;
    }
}