GFG数组领导者问题：优化超时Java代码并计算时间复杂度

Hey, let's break down why your code is hitting the time limit and fix it up without changing the core requirement of finding leader elements (elements >= all elements to their right).

What's Wrong with the Original Code? #

Your current approach has two critical issues that make it impossible to handle large N (up to 1e7):

• O(n²) Time Complexity: For each element, you recursively compare it to every element on its right. For n=1e7, this means ~1e14 operations—way too slow for a 3-second time limit.
• Recursion Stack Overflow: Both the input parsing and leader checking use recursion with depth equal to n. For n=1e7, this will immediately crash with a stack overflow error, which also contributes to the timeout.

Optimized Solution (O(n) Time, O(1) Extra Space) #

The key insight is to traverse the array from right to left and keep track of the largest element we've seen so far. This way, we only need one pass through the array:

• The rightmost element is always a leader, so we start with it as our current maximum.
• For each element moving leftwards:
  • If it's >= current maximum, it's a leader—update the current maximum to this element.
• Since we collect leaders from right to left, we can either store them in a list and reverse it, or build the output string in reverse order.

Here's the optimized code, with efficient input handling (critical for large N):

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public 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());
            int[] a = new int[N];
            
            // Efficient input parsing with StringTokenizer (faster than split for large inputs)
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }
            
            // Find leaders from right to left
            StringBuilder sb = new StringBuilder();
            int maxSoFar = a[N-1];
            sb.append(maxSoFar).append(" ");
            
            for (int i = N-2; i >= 0; i--) {
                if (a[i] >= maxSoFar) {
                    maxSoFar = a[i];
                    sb.append(maxSoFar).append(" ");
                }
            }
            
            // Reverse the result to get left-to-right order and print
            System.out.println(sb.reverse().toString().trim());
        }
        br.close();
    }
}

Key Optimizations Explained #

• Linear Time Traversal: We only loop through the array once, so time complexity is O(n)—this is perfect for n=1e7 as it will run well within the 3-second limit.
• No Recursion: All operations use loops, eliminating stack overflow risks and reducing overhead from recursive function calls.
• Efficient Input Handling: StringTokenizer is faster than split() for large strings because it avoids creating an intermediate string array, which saves memory and time.
• StringBuilder for Output: Building the output string with StringBuilder instead of multiple System.out.print calls drastically reduces I/O overhead, which is crucial for large datasets.

Time Complexity Breakdown #

• Input parsing: O(n)
• Leader finding: O(n)
• Output building: O(n)
  Total time complexity: O(n)

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