Java实现数组前三大元素查找代码单测试用例报MLE如何解决

给定大小为N的数组A，需查找数组的最大值、第二大值、第三大值，要求单测试用例时间复杂度为O(N)。

• 第一行输入为测试用例总数T
• 每个测试用例首行输入整数N表示数组A的元素个数，下一行输入N个以空格分隔的数组元素

• 1 <= T <= 100
• 3 <= N <= 10^6
• 1 <= A[i] <= 10^9

编写的求解代码可通过绝大多数测试用例，仅1个测试用例运行时提示*MLE（内存超限）*错误，附完整Java源码如下，寻求可通过该测试用例的优化方案：

import java.io.*; // for handling input/output
import java.util.*; // contains Collections framework

// don't change the name of this class
// you can add inner classes if needed
class Main {
    public static void main (String[] args) {
                      // Your code here
                      Scanner sc = new Scanner(System.in);
                      int size = sc.nextInt();
                   
                        while(size>0){
                           int n = sc.nextInt();
                          int myarray[] = new int [n];
                          for(int j=0; j<n;j++) {
                          myarray[j]= sc.nextInt();
                      }
                      printNumber(myarray);
                      size--;
                        }                
    }
    public static void printNumber(int [] myarray){
        int first=0;
        int second=0;
        int third=0;
        
        for(int i=0;i<myarray.length;i++){

            if (myarray[i] > first){
               third=second;
               second=first;
               first=myarray[i];
      }
      else if (myarray[i] > second){
         third = second;
         second = myarray[i];
      }
      else if (myarray[i] > third)
         third = myarray[i];
   }
   System.out.println(first+" "+second+" "+third);
        }
    }

触发MLE的核心原因有两个：

1. 无意义的全量数组存储：查找前三大值不需要保存整个数组的所有元素，单个数组长度到1e6时，仅int数组本身就要占用约4MB堆内存，叠加多测试用例的内存残留，很容易触碰内存阈值。
2. Scanner输入类的额外开销：Scanner本身解析效率低，内部维护的输入缓存会持有额外的内存占用，处理百万级输入时内存开销会进一步升高。

• 把空间复杂度从O(N)降到O(1)：取消存储全量数组的逻辑，读取每个数字时直接参与前三大值的比较，全程只需要维护3个记录最值的变量即可。
• 替换输入类为BufferedReader：相比Scanner，BufferedReader的输入缓冲区设计更高效，解析大输入时内存占用更低、速度更快。
• 原有比较前三大值的逻辑本身是正确的，不需要修改。

优化后的可通过代码如下：

import java.io.*;

class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            int n = Integer.parseInt(br.readLine());
            String[] numStrs = br.readLine().split(" ");
            int first = 0, second = 0, third = 0;
            for(int i=0; i<n; i++){
                int num = Integer.parseInt(numStrs[i]);
                if(num > first){
                    third = second;
                    second = first;
                    first = num;
                } else if(num > second){
                    third = second;
                    second = num;
                } else if(num > third){
                    third = num;
                }
            }
            System.out.println(first + " " + second + " " + third);
        }
    }
}

注：如果需要进一步压缩输入内存，还可以实现逐字节读取输入手动解析数字，不需要把整行字符串分割成数组，上述优化版本已经足够通过常规OJ的内存限制测试用例。

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