怎么查看BIOS文件地址？从UEFI分区到固件备份的定位指南
2026/10/18 12:58:56
最近不少刷PTA的同学卡在实验7-2-8“找鞍点”这道题上。说实话，这道题在二维数组章节里属于难度中等偏下的，但它非常经典——考察的是你对二维数组遍历、嵌套循环、条件判断还有“状态标志位”的理解程度。所谓鞍点，就是矩阵中某个元素，在它所在行是最大值，同时在它所在列是最小值。听起来很简单，但真上手写代码就会发现坑不少：鞍点可能不存在、可能不唯一、可能一行里有好几个并列最大值，甚至输出格式写不对都会被判错。这篇文章我把这道题从读题、设计算法、写代码到调试避坑的完整过程拆开讲一遍，C语言为主，思路对其他语言同样适用。正在学二维数组的同学，或者想复习经典矩阵算法的朋友，都可以从里面拿走一份能直接复用的方案。
1. 这道题到底在考什么
1.1 题目描述与输入输出要求
PTA平台上的“找鞍点”题目描述通常长这样：输入一个正整数n，随后n行每行输入n个整数，构成一个n阶方阵。请找出矩阵中的鞍点，输出它所在的行号和列号，如果不存在鞍点，则输出“NONE”。部分版本会要求输出“NO”，甚至有的版本列号从1开始计数，所以拿到题第一件事一定是看样例，确定行号列号是0基还是1基。
标准样例往往是这样的：
输入： 4 1 7 4 1 4 8 3 6 1 6 1 2 0 7 8 9 输出： 2 1我们来手动验证一下：第2行（0基编号）是1、6、1、2，最大值是6，在第1列；第1列是7、8、6、7，最小值是6；因此位置(2,1)就是鞍点。这个样例能帮你直观理解“行最大、列最小”的含义。
1.2 鞍点的定义和容易踩的定义坑
数学上，鞍点是一个函数在某点沿一个方向取极大、沿另一个方向取极小的位置。在矩阵题里，定义被简化成一句话：某个元素在其所在行上是最大值，同时在其所在列上是最小值。
这里有几个细节容易被忽略：
第一，并列值算不算。如果一行里有多个元素同时等于最大值，那么它们每一个都“在该行是最大值”，都有资格被检查。同样，一列里有多个元素同时等于最小值，每一个都“在该列是最小值”。所以判断时要用严格小于/大于来比较，不能用小于等于/大于等于。
第二，鞍点不一定存在。比如矩阵对角线全是1、其余全是0的情况，可能找不到满足条件的点。题目专门设计成可能输出“NONE”，就是为了考察你处理“无解”分支的能力。
第三，鞍点不唯一。某些矩阵中会出现多个鞍点，题目一般要求输出第一个找到的。按行从0到n-1、列从0到n-1的顺序扫描，第一个满足条件的点就是标准答案。
2. 算法思路：从暴力到预计算
2.1 最直接的遍历法：逐个元素验证
刚学二维数组的同学，最容易想到的思路是：把矩阵里每一个元素都检查一遍，看它是否同时满足“行最大”和“列最小”。
伪代码大概是：
for 每一行i: for 每一列j: 检查第i行所有元素，是否都小于等于a[i][j] 检查第j列所有元素，是否都大于等于a[i][j] 如果两个条件同时成立，这就是鞍点，输出并结束这个思路没有任何问题，代码字面意思和题目定义完全一致，几乎不可能因为逻辑理解出错。复杂度是O(n^3)，因为外层两个循环枚举元素，内层两个循环分别扫描行和列。
PTA这道题的n一般不超过10，所以O(n^3)能轻松通过。不过你要是拿着O(n^3)的代码去面试，面试官通常不会满意。
2.2 预计算优化：先记下每行最大值和每列最小值
优化的思路是：不要检查每个元素的时候都重新扫一遍行和列，先一次性把每行的最大值、每列的最小值算好存起来。
比如用rowMax[i]存第i行的最大值，用colMin[j]存第j列的最小值。然后再次遍历矩阵的每个元素a[i][j]，判断它是否同时满足：
a[i][j] == rowMax[i] a[i][j] == colMin[j]如果两个都相等，那么a[i][j]就是鞍点。
这里可能有人会问：为什么判断行最大是用“相等”，而不是用“大于等于”？因为rowMax[i]本来就是我们预先算出来的行最大值，元素的值等于它，就说明它在这一行里是最大之一；colMin[j]同理。两个条件同时满足，说明这个元素在行里是最大，在列里是最小。
预计算方案的时间复杂度是O(n^2)，空间复杂度O(n)，用额外的两个一维数组换掉了内层的重复扫描。这在n扩大到几百时依然优秀。
2.3 两种方案怎么选
| 方案 | 时间复杂度 | 空间复杂度 | 代码量 | 适用场景 |
|---|---|---|---|---|
| 逐个验证 | O(n^3) | O(1) | 较短 | n很小，快速交题 |
| 预计算 | O(n^2) | O(n) | 稍长 | n较大，算法面试推荐 |
我的建议是：如果你现在还在初学阶段，先用暴力法把题目过了，体会一遍最原始的逻辑；然后逼自己写出预计算版本，对比两者的区别。这比单纯背代码有意义得多。做题不是目的，通过这道题理解“空间换时间”的套路才是收获。
3. 代码实现与逐段讲解
3.1 一个能正确提交的基础版本
先看一个结构清晰、能直接过PTA的C语言版本：
#include <stdio.h> int main() { int n, i, j, k; int a[10][10]; scanf("%d", &n); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { scanf("%d", &a[i][j]); } } for (i = 0; i < n; i++) { // 找第i行的最大值 int max = a[i][0]; for (j = 1; j < n; j++) { if (a[i][j] > max) { max = a[i][j]; } } // 遍历这一行所有等于max的列，检查该列是否以max为最小值 for (j = 0; j < n; j++) { if (a[i][j] == max) { int isMin = 1; for (k = 0; k < n; k++) { if (a[k][j] < max) { isMin = 0; break; } } if (isMin) { printf("%d %d\n", i, j); return 0; } } } } printf("NONE\n"); return 0; }这段代码分三步走：读入矩阵；逐行算出该行最大值；再遍历该行所有等于最大值的列，逐个检查这一列上是否没有比max更小的元素。只要有一列满足条件，就输出行列号并立即结束程序。
注意里面的return 0非常关键。它保证找到一个鞍点后立刻退出，不会继续往后找，也就不会输出多个结果。如果没有这句话，程序会在找到鞍点后继续循环，最后可能输出多个位置或者再输出一个“NONE”。
3.2 容易被扣分的重复最大值问题
很多人第一版代码是这样写的：找第i行最大值时，顺手记录最大值的列号col，然后只检查a[i][col]这一列。
// 错误示范，只取第一个最大值 int max = a[i][0]; int col = 0; for (j = 1; j < n; j++) { if (a[i][j] > max) { max = a[i][j]; col = j; } } // 只检查 col 这一列……这个写法在大多数普通样例上能过，但遇到特殊情况会挂。看下面这个反例：
2 2 1 1 2 0 2 3 3第0行的最大值是2，同时出现在第0列和第1列。第0列是2、1、2，最小值是1，所以(0,0)不是鞍点；第1列是2、2、3，最小值是2，所以(0,1)是鞍点。
如果代码只记录第一个最大值所在的列0，检查后发现不满足条件，就直接认为这一行没有鞍点，最后输出“NONE”。但正确答案是(0,1)，于是判错。
这就是我反复强调“遍历这一行所有等于max的列”的原因。只要有一个并列最大值所在列满足列最小条件，它就是鞍点。初学阶段最容易栽在这个点上，因为普通样例往往只构造唯一最大值，隐藏用例才会暴露问题。
3.3 预计算版本：更优雅的O(n^2)写法
再看预计算版本，它天然规避了重复最大值的问题：
#include <stdio.h> int main() { int n, i, j; int a[10][10]; int rowMax[10], colMin[10]; scanf("%d", &n); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { scanf("%d", &a[i][j]); } } // 计算每行最大值 for (i = 0; i < n; i++) { rowMax[i] = a[i][0]; for (j = 1; j < n; j++) { if (a[i][j] > rowMax[i]) { rowMax[i] = a[i][j]; } } } // 计算每列最小值 for (j = 0; j < n; j++) { colMin[j] = a[0][j]; for (i = 1; i < n; i++) { if (a[i][j] < colMin[j]) { colMin[j] = a[i][j]; } } } // 遍历矩阵找鞍点 for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (a[i][j] == rowMax[i] && a[i][j] == colMin[j]) { printf("%d %d\n", i, j); return 0; } } } printf("NONE\n"); return 0; }为什么预计算版本不怕重复最大值？因为rowMax[i]只存值，不存列号。只要a[i][j]等于行最大值，它就进入判断；而判断里又要求它同时等于列最小值。这样每一行的所有并列最大值都会自然被检查到，不会出现“只认第一个位置”的遗漏。
这个版本还有一个好处：逻辑分层清晰。先算行统计量，再算列统计量，最后组合判断。如果你以后做二维前缀和、矩阵动态规划，会发现同样的三步结构反复出现。
3.4 输出细节与主函数返回
PTA判题对输出格式非常敏感。鞍点输出格式一般是%d %d，中间一个空格，结尾换行。如果你多打一个空格、少打一个换行，或者用中文逗号，都可能被判格式错误。
“NONE”字符串的大小写也要严格匹配题目要求。我见过有的题目要求输出“NONE”，有的要求“NO”，甚至还有要求输出“None”的版本，所以不要凭记忆，每次提交前回看一眼输出格式。
代码结构上，建议找到鞍点后立刻return 0，这样不会继续执行到后面的printf("NONE")。有人喜欢用一个flag变量标记是否找到，最后统一判断，也可以，但要注意别把flag的作用域和更新时机写错，否则会出现“明明找到了却仍然输出NONE”的诡异问题。
4. 调试与常见问题速查
4.1 边界条件：1x1矩阵、单行、单列
边界条件永远是这类题最容易翻车的地方。先看1x1矩阵：
1 5一个元素5，它在唯一的行上是最大值，在唯一的列上是最小值，所以它必然是鞍点，输出0 0。上面的代码里，max被初始化为a[0][0]，内层循环从1开始，循环体不会执行；列最小值同理；最后判断a[0][0] == rowMax[0] && a[0][0] == colMin[0]成立，因此能正确输出。只要初始化得当，1x1矩阵不会出问题。
那如果n不等于方阵而是矩形呢？题目如果明确写“n阶方阵”，那输入一定是正方形；但有些变体题给的是m行n列。遇到矩形矩阵，只需要把行数、列数分别存成两个变量，循环范围跟着改即可。核心判断逻辑完全一样。
4.2 输出字符串到底是NONE还是NO
这个坑看起来低级，但每年都有不少同学栽进去。PTA这个平台上的同一道题，在不同课程、不同老师布置时，输出要求可能有细微差异。有的版本要求鞍点不存在时输出“NONE”，有的版本要求输出“NO”，还有些变体要求输出“not found”之类的文本。
判断方法只有一个：仔细看题目原文的输出格式说明。不要在评论区看到别人写“NONE”就直接抄，因为你们选的可能是不同版本。提交前做一次自查：大小写是否完全一致？有没有拼写错误？字符串里有没有多余空格？
4.3 常见错误对照表
| 错误现象 | 可能原因 | 解决办法 |
|---|---|---|
| 样例输出对，但隐藏用例判错 | 只检查了第一个最大值所在列，漏掉并列最大值 | 遍历该行所有等于max的列，或用预计算方案 |
| 总是输出NONE | 判断列最小用了<=，把等于最大值的元素当成“不满足最小” | 用严格小于<来判断是否存在更小元素 |
| 输出多个结果 | 找到鞍点后没有return或没有置标志位 | 找到后立即return 0 |
| 数组越界或读入错乱 | 循环边界写成<= n | 检查for循环条件，数组下标范围是0 ~ n-1 |
| 输出格式错误 | 输出字符串拼写错误、空格或换行不对 | 严格按题目格式，复制粘贴输出字符串最稳妥 |
| 大n时运行超时 | 暴力三层循环在n较大时吃力 | 改为预计算，降到O(n^2) |
4.4 自己动手构造测试用例
刷题不能只靠评测系统教做人，要养成自己构造用例的习惯。找鞍点这题，建议准备几类测试数据：
- 1x1矩阵，验证边界
- 简单有鞍点矩阵，验证基本输出
- 完全不存在鞍点的矩阵，验证“NONE”
- 一行有多个并列最大值的矩阵，验证不遗漏
- 一列有多个并列最小值的矩阵，验证并列值也算最小
另外推荐一个小技巧：同时写一个暴力三层循环版本和预计算版本，用随机生成的矩阵不断对拍。两个版本输出不一致时，用暴力版的输出作为参考，很快就能定位优化版的逻辑哪里写歪了。这种“对拍”的思路，在做更复杂的算法题时也特别好用。
5. 鞍点之外：这道题带来的算法思维
5.1 从二维数组题到矩阵算法
“找鞍点”表面上是二维数组练习题，背后其实是矩阵算法里非常典型的“行列统计量组合”问题。你先对每一行算一个统计量（最大值），对每一列算一个统计量（最小值），最后做元素级别的匹配。这个套路可以迁移到很多地方。
比如二维前缀和，它先预处理出从左上角到每个位置的和，之后任何子矩阵的求和都变成O(1)的查表。再比如矩阵动态规划，往往需要先预处理某一行或某一列的最值、累加值，再递推后续状态。理解和掌握“先聚合、再查询”的思想，比会做这一道题值钱得多。
遇到更复杂版本的新题，第一反应不应该是一头扎进循环里，而是先想清楚：哪些信息是重复计算的？能不能提前算好？需要同时用到行和列的信息时，是用两个数组，还是需要某种更复杂的结构？想清楚这几步，代码写起来会很顺。
5.2 鞍点在真实世界里的影子
鞍点不是教材里的抽象概念，它在实际领域里经常出现。博弈论里的零和博弈中，鞍点对应一种纯策略纳什均衡：局中人一方选择某个策略时收益最大，另一方在同样的策略组合下损失最小，双方都没有单方面改变策略的动力。
深度学习里也常听到“鞍点”这个词。高维损失函数曲面上，梯度为零的位置不一定是局部最小值，很多点沿着一个方向看是极小值，沿着另一个方向看却是极大值，这就是优化算法容易陷入的鞍部区域。理解矩阵鞍点的判断逻辑，对理解这些应用场景多少有点帮助。
5.3 如果想继续练，这些变体题值得挑战
“找鞍点”本身还能演化出很多变体。比如改成输出所有鞍点，那么就不能在找到第一个后return，要用数组记录结果最后统一输出。改成判断是否存在鞍点并输出个数，那更简单，把return 0改成计数器自增。改成非方阵，只需要把行循环和列循环的范围改成各自的实际大小。
还有一个常见的进阶版：如果不需要找鞍点，而是判断矩阵是否“严格对角占优”，核心依然是行和列的统计信息计算，只不过判断条件变成了“对角线元素绝对值大于本行其他元素绝对值之和”。这类问题练多了，你会慢慢发现，二维数组的题目翻来覆去就是那几种统计套路，掌握了就一通百通。
我个人在这道题上吃过不小的亏。第一次提交时用的就是“只记录第一个最大值列号”的写法，样例全过，结果隐藏用例挂了两个。后来我慢慢养成一个习惯：凡是“找一个满足条件的元素”的题目，动笔前先问自己三个问题——这个元素一定存在吗？存在的话唯一吗？如果有并列值，题目怎么定义？把这三个问题想清楚，再开始写代码，基本不会在边界条件和隐藏用例上翻车。希望这篇文章也能帮你少走一点弯路，把二维数组这章真正学扎实。