鱼类进化编程问题求助：Java实现遇超时与答案错误

问题描述 #

Namita拥有魔法鱼，这类鱼能进化成更大的鱼类：当小鱼碰到更大或同等尺寸的鱼时，大鱼会消失，小鱼进化到该大鱼的尺寸。为避免意外进化，鱼被放在线性排列的独立单元格中。现在要选出进化次数最多的鱼，标注+1的鱼只能向右进化，标注-1的鱼只能向左进化。

注意：鱼会优先进化途中遇到的第一条更大的鱼，比如序列[5,12,10,11,13]中，尺寸5的鱼进化路径是5→12→13（进化2次），而非5→10→11→13。如果多条鱼进化次数相同，选尺寸更大的那条。

输入格式 #

• 第一行输入整数t，表示测试用例数量。
• 每个测试用例：
  • 第一行输入整数n，表示鱼的数量。
  • 第二行输入n个空格分隔的整数，代表鱼的尺寸。
  • 第三行输入n个空格分隔的整数（只能是+1或-1），代表进化方向。

输出格式 #

对每个测试用例，输出进化次数最多的鱼的尺寸及其进化方向（Right对应+1，Left对应-1）。

我的实现与问题 #

我通过从右到左遍历计算rightEvolution数组（记录每条鱼向右进化的次数），从左到右遍历计算leftEvolution数组（记录每条鱼向左进化的次数），再从中找出最大值。但Java实现遇到了超时（TLE）和答案错误的问题，代码如下：

import java.util.*;

public  class Solution{

    public static void main(String [] args)
    {
        Scanner sc =new Scanner(System.in);

        int t= sc.nextInt();
        while(t-->0)
        {
        int n =sc.nextInt();
        int [] sizes =new int[n];
        int [] direction= new int[n];

        for(int i=0;i<n;i++)
         sizes[i] = sc.nextInt();

        for(int i=0;i<n;i++)
          direction[i]  =sc.nextInt();

       int [] rightEvolution = new int[n];
          //max evolution that every fish can achive while moving to right direction ,
          //   so we have to now from right to left
           rightEvolution[n-1]=0;
          for(int i=n-2;i>=0;i--)
          {
             int j=i+1;
             int s=sizes[i];
              while( j<=n-1 && s>=sizes[j] )
                       j++;
                if(j<=n-1)
              rightEvolution[i] =rightEvolution[j]+1;
                else
                rightEvolution[i]=0;
          }

        int [] leftEvolution =new int[n];
            leftEvolution[0] =0;
         for(int i=1;i<n;i++)
         {
            int j=i-1;
             int s=sizes[i];
              while(j>=0 && s>=sizes[j])
                   j--;
              if(j>=0)
              leftEvolution[i]=leftEvolution[j]+1;
              else 
               leftEvolution[i]=0;
         }
        //  System.out.println("Right Evolution");
        //  for(int i=0;i<n;i++)
        //    System.out.print(rightEvolution[i]+" ");
          
        //   System.out.println();
        //    System.out.println("left evolution");
        //   for(int i=0;i<n;i++)
        //   System.out.print(leftEvolution[i]+" ");

         //find the maximum right evolution 
        int  maxr=0;
        int initSizeR=0;
         for (int i=0;i<n;i++)
           {
             if(direction[i]==1)
              {
                 if(rightEvolution[i]>maxr)
                  {
                    maxr=rightEvolution[i];
                    initSizeR=sizes[i];
                  }
                 else if(rightEvolution[i]==maxr &&initSizeR<sizes[i])
                  {
                       initSizeR=sizes[i];
                  }
              }
           }

           //find the maximum size in left evolution
          int maxl=0;
          int initSizeL=0;
           for(int i=0;i<n;i++)
           {
             if(direction[i]==-1)
             {
             if(leftEvolution[i]>maxl)
             {
               maxl=leftEvolution[i];
               initSizeL=sizes[i];

             }
           else  if(leftEvolution[i]==maxl && initSizeL<sizes[i])
              {
                initSizeL=sizes[i];
              }
             }
           }


           // find the maximum evolution out of  maximum left and right evolution and print the result
                if(maxr>maxl)
                {
                        System.out.println(initSizeR+" Right");
                }
                else if (maxr<maxl)
                {
                        System.out.println(initSizeL+" Left");
                }
                else if(maxr==maxl)
                {
                       if(initSizeL<initSizeR)
                          System.out.println(initSizeR+" Right");
                       else
                           System.out.println(initSizeL+" Left");
                }
             


        } 
    }
}

请求帮助优化代码解决超时问题，并排查答案错误的原因。

问题分析与优化方案 #

1. 超时原因：暴力遍历导致O(n²)时间复杂度 #

你的代码中计算rightEvolution和leftEvolution时，每条鱼都用while循环逐个查找下一个更大的鱼，最坏情况下（比如鱼的尺寸严格递减/递增），时间复杂度会达到O(n²)，当n很大时就会超时。

2. 答案错误原因：进化逻辑理解偏差 #

题目中，鱼进化后会变成被吃掉的大鱼的尺寸，之后应该继续用进化后的尺寸寻找下一个更大的鱼。但你的代码里始终用原始尺寸sizes[i]去查找，这就导致计算的进化次数错误。比如例子中的5→12→13，你的代码中5第一次找到12后，应该用12的尺寸去查找下一个更大的鱼（13），但你的代码还是用5去查找，完全不符合逻辑。

3. 优化方案：用单调栈实现O(n)时间复杂度的计算 #

我们可以用单调栈来高效找到每个鱼进化路径上的下一个目标，同时记录进化次数：

核心思路

• 计算向右进化次数时，从右往左遍历，维护一个单调递减的栈（栈中保存鱼的最终进化尺寸和对应进化次数）。
• 计算向左进化次数时，从左往右遍历，维护一个单调递减的栈。
• 对于每条鱼，弹出栈中所有尺寸≤当前鱼的元素，剩下的栈顶就是第一个能被当前鱼吃掉并进化的目标，当前鱼的进化次数为目标的进化次数+1，最终尺寸等同于目标的最终尺寸。

修正后的代码示例

import java.util.*;

public class Solution {
    static class FishInfo {
        int size;
        int count;
        FishInfo(int size, int count) {
            this.size = size;
            this.count = count;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 加快输入速度，避免超时
        sc.useDelimiter("\n");
        int t = Integer.parseInt(sc.next());
        while (t-- > 0) {
            int n = Integer.parseInt(sc.next());
            int[] sizes = Arrays.stream(sc.next().split(" ")).mapToInt(Integer::parseInt).toArray();
            int[] directions = Arrays.stream(sc.next().split(" ")).mapToInt(Integer::parseInt).toArray();

            int[] rightEvolution = new int[n];
            Deque<FishInfo> rightStack = new ArrayDeque<>();
            // 从右往左计算向右进化次数
            for (int i = n - 1; i >= 0; i--) {
                int currentSize = sizes[i];
                int count = 0;
                // 弹出所有尺寸<=当前尺寸的鱼，因为当前鱼可以吃掉它们
                while (!rightStack.isEmpty() && rightStack.peek().size <= currentSize) {
                    rightStack.pop();
                }
                if (!rightStack.isEmpty()) {
                    FishInfo next = rightStack.peek();
                    count = next.count + 1;
                    // 当前鱼吃掉next后，最终尺寸是next的最终尺寸，压入栈
                    rightStack.push(new FishInfo(next.size, count));
                } else {
                    // 没有更大的鱼，压入当前尺寸，次数0
                    rightStack.push(new FishInfo(currentSize, 0));
                }
                rightEvolution[i] = count;
            }

            int[] leftEvolution = new int[n];
            Deque<FishInfo> leftStack = new ArrayDeque<>();
            // 从左往右计算向左进化次数
            for (int i = 0; i < n; i++) {
                int currentSize = sizes[i];
                int count = 0;
                // 弹出所有尺寸<=当前尺寸的鱼
                while (!leftStack.isEmpty() && leftStack.peek().size <= currentSize) {
                    leftStack.pop();
                }
                if (!leftStack.isEmpty()) {
                    FishInfo next = leftStack.peek();
                    count = next.count + 1;
                    leftStack.push(new FishInfo(next.size, count));
                } else {
                    leftStack.push(new FishInfo(currentSize, 0));
                }
                leftEvolution[i] = count;
            }

            // 寻找最优解
            int maxCount = -1;
            int bestSize = -1;
            String bestDir = "";

            for (int i = 0; i < n; i++) {
                int currentCount = 0;
                String dir = "";
                if (directions[i] == 1) {
                    currentCount = rightEvolution[i];
                    dir = "Right";
                } else {
                    currentCount = leftEvolution[i];
                    dir = "Left";
                }

                // 优先级：次数多 > 次数相同则尺寸大
                if (currentCount > maxCount) {
                    maxCount = currentCount;
                    bestSize = sizes[i];
                    bestDir = dir;
                } else if (currentCount == maxCount) {
                    if (sizes[i] > bestSize) {
                        bestSize = sizes[i];
                        bestDir = dir;
                    }
                }
            }

            System.out.println(bestSize + " " + bestDir);
        }
        sc.close();
    }
}

额外优化：输入速度

原代码用sc.nextInt()逐个读取，当输入量很大时会比较慢，改用sc.useDelimiter("\n")配合split和stream可以加快输入速度，避免超时。

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