在不改变程序逻辑的情况下优化给定的解决方案。同时计算时间复杂度

Question

这是一个GFG实践问题，因此无法配置编译器

问题
给定正整数数组。你的任务是找到阵中的首领。注意：数组中的元素如果大于或等于其右侧的所有元素，则为leader。还有，最右边的元素总是一个领导者。

输入：输入的第一行包含一个表示测试用例数量的整数T。下面是T测试用例的描述。每个测试用例的第一行包含一个表示数组大小的整数N。第二行包含N个空格分隔的整数A1,A2,...,a表示数组的元素。

输出：打印所有领导人。

约束:
1<=T<=100
1<=N<=107
0<=Ai<=107

我的解决方案：

import java.util.*;
import java.io.*;
import java.lang.*;
public class Main
{  
    static BufferedReader z1 = new BufferedReader(new InputStreamReader(System.in));
      public static void main (String[] args)throws Exception
    {    
        int T=Integer.parseInt(z1.readLine());
         while(T-- > 0)
        {      
              int N=Integer.parseInt(z1.readLine());
           solution ob = new solution();
              int []a=new int[N];
              a=ob.input(N,z1);
              int x=0;
              ob.leader(a,N,x);
        }
    }
}
class solution
{  
    static int[] input(int N, BufferedReader z1)throws Exception
   {    
         int a[]=new int[N];
          String s=z1.readLine();
          String []str=s.split(" ");
          /* for(int y=0;y<N;y++)
             a[y]=Integer.parseInt(str[y]); */
          toInts(str,a,0);
            return a;
   } 
    
    static void toInts(String[] strings, int[] ints, int start) {
    if (start > strings.length - 1) {
        return;
    }
    ints[start] = Integer.parseInt(strings[start]);
    toInts(strings, ints, start+1);
}
   
    static void leader(int []a,int N,int x)
   {    
           int count = 0;
           if(x==N-1)
            System.out.println(a[x]);
            else
            { 
               count = compare(a,x,x+1,count,N);
             /* for(int y=x+1;y<N;y++)
               if(a[x]>=a[y])
                 count++; */
               if(count==(N-x-1))
                 System.out.print(a[x]);
               leader(a,N,x+1);
            }
    }
    static int compare(int []a,int x,int y,int count,int N)
    {
        if(y==N)
         return count;
        else
        {
            if(a[x]>=a[y])
             count ++;
            return compare(a,x,y+1,count,N);
        }
    }
}

错误：

Runtime Error:
Runtime ErrorTime Limit Exceeded

Your program took more time than expected.Time Limit Exceeded
Expected Time Limit 3.00sec

Answer 1

一个问题（也可能是长时间的原因）是，compare()方法一旦遇到较大的值就不会停止，因此很明显当前元素不是leader。相反，它将始终比较所有值。
对于大小为N的数组，这使得代码的运行时为O(n^2)。

这个问题可以在O(N)中解决。
从数组的右端开始，打印最后一个元素作为leader，并将其设置为当前最大值。然后左转,检查当前元素是否大于或等于最大值。如果是，则将其打印为前导，并将其设置为最大值。继续，直到到达数组的左端。

您还可以通过使用简单的for-loop替换递归的toInts（）方法来转换字符串来节省一些时间。