有一组订单金额,想找出其中最大的一笔。数据只有四条时,你一眼就能看出答案;如果有一百万条,就需要把“怎么看出来的”变成计算机能执行的步骤。
算法学习可以从这件小事开始:把问题说明白,设计有限的处理步骤,说明为什么能得到正确结果,再估算数据增加后的代价。
这个系列面向会写变量、条件判断、循环和方法的 Java 初学者。每篇围绕一个问题展开,先手动推演,再看代码,最后用边界情况和练习检查理解。无需提前学习高等数学,也不用一次记住所有算法名称。
一、这八篇怎样衔接
前四篇主要练习如何减少数组中的重复工作,后四篇开始处理递归、树和更复杂的选择过程。
| 篇目 | 用什么问题学习 | 读完应当能解释什么 |
|---|---|---|
| 本篇:复杂度与数组 | 找出最大值 | 一趟遍历为什么正确,数据增长后工作量怎样变化 |
| 第二篇:哈希表与两数之和 | 找到和为目标值的两个数 | 如何通过保存已知信息减少查找 |
| 第三篇:双指针与滑动窗口 | 找最短的达标连续区间 | 两个指针为什么能只向前走 |
| 第四篇:二分查找与边界 | 在有序数组中找第一个达标位置 | 每轮为什么能排除一半候选位置 |
| 第五篇:递归与归并排序 | 把一组数字排好序 | 如何拆分问题,并把子问题的答案合并 |
| 第六篇:栈、队列与树 | 按层读取一棵树 | 处理顺序怎样由数据结构决定 |
| 第七篇:回溯与子集 | 列出所有选择组合 | 如何尝试选择、保留答案并撤销状态 |
| 第八篇:动态规划与最少硬币 | 用最少硬币凑出指定金额 | 如何定义状态并复用已算出的最优结果 |
建议每篇至少做三件事:自己在纸上走一遍例子,运行示例,再独立完成文末练习。运行成功只能说明程序处理了当前输入;能够解释边界和变化过程,才说明你掌握了这个方法。
全系列示例使用 Java 17 及以上版本,只依赖 JDK。可以下载完整示例包和运行说明。每篇也单独提供对应的 .java 文件。
二、先写清输入、输出和约束
现在的问题是:给定一组整数,返回其中的最大值。
输入:[120, 80, 260, 150]输出:260下笔写代码以前,先回答三个问题。
返回值还是位置? 这里返回数字 260。如果题目要“最大值第一次出现的位置”,返回的应是下标 2,代码就需要同时记录位置。
数字可以重复或为负数吗? 可以。例如 [5, 5, 2] 返回 5,[-8, -3, -12] 返回 -3。
空数组怎么办? 空数组没有最大值。本文约定空数组或 null 都抛出 IllegalArgumentException,告诉调用方输入不符合要求。这里不能返回 0 或 -1 表示失败,因为它们也可能是合法答案。
把这些约定写清楚,后面就能区分“算法写错了”和“双方对问题的理解不同”。
示例虽然用订单金额引入,但代码处理的是普通整数。真实金额应明确货币单位、精度和范围;本篇不涉及金额计算。
三、数组里存的是什么
数组把一组同类型的元素放在一起,通过下标访问。Java 中长度为 n 的数组,有效下标是 0 到 n - 1。
下标: 0 1 2 3数值: 120 80 260 150values[2] 直接取得第三个元素。已经知道下标时,访问一个数组元素可以按常数时间理解;但是“最大值在哪个下标”还不知道,因此仍需检查数据。
数据结构描述数据如何组织,算法描述如何处理这些数据。这里数组是数据结构,“从左到右保留最大值”是算法。后面换成哈希表或队列,也是在为某种处理方式选择更合适的数据组织。
四、手动做一遍,再翻译成代码
可以先把第一个数当成当前最大值,之后逐个比较:遇到更大的数就更新,否则保持原值。
| 当前处理的数 | 比较前的最大值 | 处理后的最大值 |
|---|---|---|
| 120 | 尚未设置 | 120 |
| 80 | 120 | 120 |
| 260 | 120 | 260 |
| 150 | 260 | 260 |
我们只需要记住一个数字 best。已经看过的数据,不必反复再查。
下面是完整的 ArrayScan.java,也可以直接下载源码:
public class ArrayScan { public static int max(int[] values) { if (values == null || values.length == 0) { throw new IllegalArgumentException("values must not be empty"); } int best = values[0]; for (int i = 1; i < values.length; i++) { if (values[i] > best) { best = values[i]; } } return best; }
public static void main(String[] args) { System.out.println(max(new int[] {120, 80, 260, 150})); System.out.println(max(new int[] {-8, -3, -12})); }}将文件保存为 ArrayScan.java,在文件所在目录执行:
javac -encoding UTF-8 ArrayScan.javajava ArrayScan应当输出:
260-3文件名需要与 public class ArrayScan 一致。javac 负责编译,java ArrayScan 运行这个类的 main 方法,不需要在类名后添加 .java 或 .class。
为什么从第一个元素开始
如果写成 int best = 0,输入全是负数时,best 就一直保持为 0,得到一个根本不在数组中的答案。
使用 values[0] 初始化,保证候选答案来自实际输入。第一个元素已经处理过了,所以循环从下标 1 开始。
怎样说明这段程序是正确的
观察循环执行过程中始终成立的一句话:
每处理完一个位置,
best就是从数组开头到这个位置的最大值。
开始时只处理了第一个数,这句话成立。随后加入一个数,如果它更大就替换,否则原最大值仍然有效。如此重复,直到最后一个数也处理完,best 就是整个数组的最大值。
这种在循环前后持续成立的性质,叫作循环不变量。入门时不必急着写形式化证明,但要能用自己的话说清“已经处理的部分现在满足什么条件”。
五、时间复杂度怎样看
假设数组长度为 n。初始化之后,一共进行 n - 1 次大小比较。数据从一千条变成一万条,比较次数大约也扩大十倍。
我们通常把这种线性增长记为 O(n)。时间复杂度关注输入规模增加时工作量的增长方式,不直接表示运行多少毫秒。
大 O 表示渐近上界;本系列会尽量给出能反映算法增长速度的紧致估计。初学时先学会数主要操作,不必一开始就钻研符号定义。
例如,先遍历一遍求最大值,再遍历一遍求最小值,总工作量大约是 2n,通常仍写成 O(n)。常数没有消失,只是在描述增长阶时不单独保留。
| 常见增长阶 | 直观例子 | 数据规模增加时的工作量趋势 |
|---|---|---|
| O(1) | 根据已知下标读取数组元素 | 大致不随规模增长 |
| O(log n) | 在有序数组中反复缩小一半搜索范围 | 数据量翻倍,只增加少量步骤 |
| O(n) | 扫描数组找最大值 | 数据量翻倍,工作量大约翻倍 |
| O(n log n) | 归并排序 | 数据量翻倍,工作量略高于翻倍 |
| O(n²) | 枚举每一对不同位置 | 数据量翻倍,工作量大约变为四倍 |
| O(n · 2ⁿ) | 生成并复制保存全部子集 | 每增加一个元素,子集数翻倍,复制成本也增加 |
表中表达的是对应典型算法的主要增长趋势,不能把大 O 上界直接当成精确操作次数。
两层循环就一定是 O(n²) 吗
要数循环总共执行了多少次,不能只数代码缩进。
如果外层走 n 次,内层每次都重新走 n 次,总次数就是 n × n。但如果两个指针各自只从头走到尾,即使语法上出现嵌套循环,总移动次数也可能只有约 2n。第三篇会遇到这种情况。
此外,要说明分析的是哪一种情况。查找某个值可能第一步就找到,也可能检查完整个数组;它的最好情况是 O(1),最坏情况是 O(n)。本文求最大值无论数据顺序如何,都要扫描完整个数组。
六、空间复杂度要算什么
求最大值时,除了输入数组,只使用了 best、i 等固定数量的变量。数组变长后,这部分存储需求不会按比例增长,所以辅助空间复杂度为 O(1)。
如果为了处理数据,额外创建一个长度为 n 的数组,辅助空间就变成 O(n)。递归函数的调用栈也占空间,不能因为没有显式创建数组就忽略。
本系列会区分输入、返回结果和处理时使用的辅助空间。例如,第七篇需要返回全部子集,结果本身就可能很大;说“辅助空间 O(n)”时,需要同时说明是否排除了输出。
算法常见的一种优化,就是多保存一些信息来减少重复计算。第二篇的哈希表会展示这种“用额外空间减少查找”的做法。
七、用边界情况检查理解
除了正常例子,还应该考虑最小输入、重复值和极端值。
| 输入 | 按本文约定的结果 | 检查目的 |
|---|---|---|
[7] | 7 | 只有一个元素时,循环可以一次也不执行 |
[5, 5, 5] | 5 | 相等时不更新也正确 |
[-8, -3, -12] | -3 | 初始化不能凭空使用零 |
[Integer.MIN_VALUE] | Integer.MIN_VALUE | 合法极值不能被当成失败标记 |
[] 或 null | 抛出参数异常 | 非法输入有明确处理方式 |
运行时间也值得观察,但不要用一次小输入的毫秒数判断算法优劣。JVM 预热、机器负载和输入分布都会影响测量;先理解增长阶,再在真实规模和环境下做性能验证。
八、练习:找出第二大的不同数字
现在把问题改成:返回第二大的不同数字。
[5, 1, 5, 3] → 3[-2, -9, -4] → -4[7, 7] → 不存在注意,“第二大”不是排序后第二个位置,因为最大值可能重复。
先写出输入输出约定,再尝试一趟遍历。提示:维护最大值和第二大值,并用单独的布尔状态表示第二大值是否已经存在;也可以在返回时使用 OptionalInt。不要直接拿 Integer.MIN_VALUE 作为“不存在”的唯一标记,它也可能出现在输入中。
完成后,检查空数组、全相等、全负数、最大值重复和极值输入。你应该能够说明每次更新后两个候选值分别代表什么,并分析出 O(n) 时间和 O(1) 辅助空间。
下一篇继续处理数组,但问题变成“找出两个和为目标值的数”。当直接枚举需要重复检查大量组合时,我们会学习如何把已经看到的信息存下来:哈希表与两数之和。
If this article helped you, please share it with others!
Some information may be outdated






