本文详解在未排序数组中查找最大值的最优策略——使用单次线性遍历，时间复杂度 o(n)、空间复杂度 o(1)，远优于排序（o(n log n)）或优先队列（o(n log n) 时间 + o(n) 空间）。
本文详解在未排序数组中查找最大值的最优策略——使用单次线性遍历，时间复杂度 o(n)、空间复杂度 o(1)，远优于排序（o(n log n)）或优先队列（o(n log n) 时间 + o(n) 空间）。
在面试或高性能场景中，「查找数组最大值」看似简单，却常被用作考察算法直觉与复杂度意识的关键题。题目明确要求：程序应在找到最大值后立即终止，无需后续操作；且需优先保障大规模数组下的执行效率。此时，Arrays.sort() 或 PriorityQueue 不仅过度设计，更会显著拖慢性能。
✅ 最优解：单次遍历（One-Pass Linear Scan）
只需一次从左到右的扫描，维护一个当前最大值变量即可。该方案具备以下不可替代的优势：
- 时间复杂度：O(n) —— 严格遍历每个元素一次，无冗余比较；
- 空间复杂度：O(1) —— 仅使用常量级额外存储；
- 提前终止？无需！ 因为最大值可能出现在最后一个位置，必须检查全部元素；但逻辑上“找到即返回”，不进行任何多余计算（区别于排序后取末尾——那本质是“算完再取”，已违背“找到即止”的意图）。
以下是健壮、可直接用于生产环境的 Java 实现：
public static int getLargestNumber(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array must not be null or empty");
}
int max = array[0]; // 以首元素初始化，避免 Integer.MIN_VALUE 在全负数时失效
for (int i = 1; i max) {
max = array[i];
}
}
return max;
}
? 关键改进说明：
- 使用 array[0] 初始化 max，而非 Integer.MIN_VALUE。后者在输入全为负数（如 [-5, -2, -10]）时逻辑正确，但语义上不够直观；而以首元素为基准更符合“比较过程”的自然逻辑，也便于泛型扩展。
- 显式校验空/null 输入——这是工业级代码的必备防御性编程实践。
❌ 为什么不选排序（Arrays.sort）？
你的初始解法：
Arrays.sort(array); // 原地排序，O(n log n) return array[array.length - 1];
问题在于：
- 排序会彻底重排整个数组，即使你只关心一个值；
- 对于含百万级元素的数组，O(n log n) 比 O(n) 慢数倍（例如 n=10⁶ 时，log₂n ≈ 20，开销放大20倍）；
- 违反“程序应尽快结束”的要求——排序完成前无法返回结果。
❌ 为什么优先队列（PriorityQueue）也不合适？
有人可能想到：建最大堆，poll() 一次得最大值。但注意：
PriorityQueue<integer> pq = new PriorityQueue(Collections.reverseOrder()); for (int x : array) pq.offer(x); // O(n log n) 建堆 return pq.poll(); // O(1)</integer>
- 建堆本身已是 O(n log n)，且需 O(n) 额外空间存储堆；
- 即使使用 heapify（O(n)），Java 标准库 PriorityQueue 并不提供原地构造，仍需复制数据；
- 核心矛盾：为获取一个极值，引入了结构化数据结构的开销——本末倒置。
? 扩展思考（面试加分项）
若面试官追问，可主动提出延伸方向，展现工程思维：
-
泛型支持：将方法升级为
> T findMax(T[] array)，适配字符串、自定义对象等； - 流式 API（Java 8+）：Arrays.stream(array).max().orElseThrow(...) —— 语义清晰，底层仍是 O(n) 遍历，但需注意装箱开销（对 int[] 需用 IntStream）；
- 并行化？ 对超大数组（如 GB 级），可考虑分段并行求局部最大值再归并，但需权衡线程开销，通常非必要。
✅ 总结
| 方法 | 时间复杂度 | 空间复杂度 | 是否满足“找到即止” | 推荐指数 |
|---|---|---|---|---|
| 单次遍历 | O(n) | O(1) | ✔️（逻辑最简，无冗余） | ⭐⭐⭐⭐⭐ |
| Arrays.sort() | O(n log n) | O(1) 或 O(n) | ❌（必须完成全部排序） | ⭐ |
| PriorityQueue | O(n log n) | O(n) | ❌（建堆即耗尽资源） | ⭐ |
记住：最简单的解法，往往就是最高效的解法。面对基础问题，先问自己——“我是否在用火箭打蚊子？”
