Java代码优化求助：O(n²)复杂度超时，求优化思路

嘿，我来帮你搞定这个超时的问题！你的代码逻辑完全正确，但嵌套循环导致了O(n²)的时间复杂度——当数组规模变大（比如n到1e4甚至1e5）时，这种写法肯定会超时。咱们可以用单调栈这个神器，把时间复杂度直接降到O(n)，完美解决问题。

问题根源 #

你的代码里，对每个元素都要往左遍历找第一个更大的元素，再往右遍历找第一个更大的元素。最坏情况下，每个元素都要遍历整个数组的一半，总操作数就是n*n，这在数据量大的时候直接“炸锅”。

优化思路：单调栈找左右第一个更大元素 #

单调栈是解决「找每个元素左右第一个更大/更小元素」这类问题的标准解法，核心思想是利用栈的单调性，让每个元素只入栈和出栈一次，从而把时间复杂度降到线性。

具体分两步走：

• 第一步：找每个元素左边第一个更大的元素位置（1-based）

  • 用栈保存数组的索引，栈内索引对应的元素保持单调递减（这样栈顶永远是当前元素左边最近的更大元素）。
  • 从左到右遍历数组：
    1. 如果栈不为空，且栈顶索引对应的元素 <= 当前元素，就弹出栈顶（这些元素不可能成为后面元素的左边更大元素了）。
    2. 栈空的话，说明左边没有更大元素，当前元素的left值为-1；否则left值是栈顶索引+1（因为题目要求位置从1开始计数）。
    3. 把当前元素的索引压入栈。

• 第二步：找每个元素右边第一个更大的元素位置（1-based）

  • 同样用单调栈，这次从右到左遍历数组：
    1. 如果栈不为空，且栈顶索引对应的元素 <= 当前元素，弹出栈顶。
    2. 栈空则right值为-1，否则是栈顶索引+1。
    3. 把当前索引压入栈。

• 最后：计算并输出结果
  遍历每个元素，直接输出left[i] + right[i]即可，还可以用StringBuilder拼接输出，减少频繁IO操作的开销。

优化后的代码示例 #

import java.util.*;
import java.io.*;

class Alpha {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        long arr[] = new long[n];
        String str[] = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(str[i]);
        }

        int[] left = new int[n];
        Stack<Integer> stack = new Stack<>();
        // 找左边第一个更大的元素位置（1-based）
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek() + 1;
            stack.push(i);
        }

        int[] right = new int[n];
        stack.clear(); // 复用栈，节省空间
        // 找右边第一个更大的元素位置（1-based）
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? -1 : stack.peek() + 1;
            stack.push(i);
        }

        // 用StringBuilder拼接输出，提升IO效率
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(left[i] + right[i]).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}

为什么这个版本更快？ #

• 每个元素只会被压入栈和弹出栈各一次，两次遍历的总操作数是O(n)，比原来的O(n²)效率提升了几个数量级。
• 用StringBuilder代替多次System.out.print，减少了IO操作的开销（频繁IO也是超时的常见原因之一）。
• 直接用数组存储结果，避免了原代码中栈反向输出的额外操作。

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