我在菜鸟教程的C经典100例里刷到练习17时刚开始是有点不屑的——一个5x5矩阵的鞍点问题无非就是找行最大、再验证列最小。但真正把代码写出来、跑完测试之后我才意识到这道题能卡住一大批初学者不是没道理的二维数组的遍历顺序、下标的对应关系、极值的初始化方式、多组数据下的标志位管理每一处都是坑。练习17的完整描述不复杂输入一个5x5的矩阵找出其中的鞍点。鞍点的定义是一个元素在它所在的行上是最大值同时在它所在的列上是最小值。如果存在鞍点输出它的位置和值如果不存在输出not found。这篇文章我打算把这道题从读题到写码、从踩坑到扩展的完整过程拆开讲一遍。不管你是刚学到数组的新手还是已经刷了几十道题想查漏补缺的老手我相信里面总有那么一两句话能让你少走弯路。文章不会只给结论我会把“为什么这样写”和“我当时是怎么翻车的”都交代清楚这样你下次遇到类似行列索引的题目时不会再犯同样的错误。1. 题目拆解鞍点到底怎么找出题人真正想考的是什么1.1 原题描述与两个条件的顺序问题先看核心定义一个元素同时满足“行最大”和“列最小”就是鞍点。拿一个5x5矩阵举例1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 5 6 7 8 9这个矩阵里(0,4)这个位置的值是5。它在第0行是最大值同时在第4列也是最小值第4列是5、6、7、8、9所以它是一个鞍点。难点在于“同时满足”这四个字。很多人第一反应是那我先找到整个矩阵的最小值看它在不在行最大或者先找到整个矩阵的最大值看它在不在列最小。这个思路是错的因为鞍点只要求“所在行”和“所在列”两个方向上的局部关系跟其他行、其他列没有关系。你必须以某个元素为基准单独考察它的行和列。1.2 为什么偏偏是5x5而不是3x3或10x105x5这个尺寸其实是有讲究的。如果题目给3x3你还可以靠肉眼把所有元素盯一遍凭直觉找出鞍点但5x5的矩阵已经复杂到没法一眼看穿必须老老实实写循环。同时5x5又不是特别大手动录入数据不会太痛苦适合作为练习题出现。更重要的是5x5意味着行和列的数量相等这会让一部分同学产生“行数等于列数所以行列下标能混用”的错觉实际上第i行和第j列是完全不同的维度。还有一个容易被忽略的点题目的5x5是固定尺寸这给了初学者一个用宏定义来管理尺寸的机会。直接用数字5写死在代码里也能跑但一旦题目改成m行n列就会改得非常痛苦。1.3 出题人真正想考察的两个能力点第一二维数组的遍历方式。你要能熟练地写“外层循环遍历行、内层循环遍历列”这种最基本的嵌套结构并且知道在什么时候需要把行列角色互换比如验证列最小的时候就得反过来遍历行。第二验证性思维的建立。找到一个候选元素之后你不能直接说“它就是鞍点”必须再去扫描一整列证明没有任何一个元素比它小。这个“先假设成立、再遍历证明”的思路是很多算法题的通用方法论。这道题练的就是这个。2. 标准解法的完整思路先定行最大值再验证列最小值2.1 主循环骨架设计我的推荐做法是外层循环遍历每一行对每一行先找出该行的最大值以及它所在的列号然后去验证这个列上是否所有元素都不小于它。如果验证通过输出结果并结束如果整行都不是鞍点继续下一行。用自然语言描述就是读入5x5矩阵。初始化标志位found为0表示还没找到。对每一行i假设第0列是这一行的最大值位置maxj 0。遍历该行第1列到第4列如果发现a[i][j] a[i][maxj]就更新maxj j。验证a[i][maxj]是否是该列的最小值遍历第maxj列的所有行只要有一个元素比a[i][maxj]小就说明它不是列最小。如果验证通过输出位置和值found设为1break。如果found仍然是0输出not found。为什么不先找列最小再验证行最大理论上是等价的但外层循环按行遍历是二维数组最自然的访问方式你只需要在一行内横向扫描就能拿到候选元素反过来如果你先按列找最小值外层循环就必须变成“列循环”这时候行列下标很容易搞混。初学者不要给自己加戏选最顺手的路线。2.2 用宏定义尺寸而不是把5写死在代码里我见过很多新手直接在代码里写a[5][5]for循环里也写j 5。这道题这么写没问题但它会养成坏习惯。更稳妥的做法是在文件开头定义#define ROW 5 #define COL 5这样做的好处是一旦题目改成“计算3x4矩阵的鞍点”你只需要改这两个宏循环、数组定义全部跟着变。更重要的是它让代码的意图更清晰——读代码的人一看就知道ROW和COL分别代表什么而不是面对一堆裸的5。2.3 为什么很多版本的答案会用到limits.h你搜这道题时可能会看到有人提到“使用stdio.h和limits.h”初学者通常不理解为什么要带limits.h。其实这是极值查找的一个通用技巧。在找行最大值时如果矩阵里可能出现负数你用0作为max的初始值就会出问题。比如一行元素是-1、-2、-3、-4、-5最大值明明是-1但如果你把max初始化为0那比较结果永远不更新最后错误地认为最大值是0。用limits.h里的INT_MIN作为初始值就能保证该行任意一个元素都比它大第一个元素就会被选中。同样在验证列最小值时用INT_MAX作为初始值保证第一个元素一定会更新这个最小值。#include stdio.h #include limits.h int max INT_MIN; for (j 0; j COL; j) { if (a[i][j] max) { max a[i][j]; maxj j; } }这是一个可以迁移到很多场景的小技巧不只是这道题。以后你写“求数组最大值”“求矩阵最小值”之类的代码都可以用INT_MIN/INT_MAX来初始化。2.4 第一版完整可运行的代码把上面的思路组合起来就是我在练习17里写的第一个可用版本#include stdio.h #include limits.h #define ROW 5 #define COL 5 int main(void) { int a[ROW][COL]; int i, j, k; int maxj; int found 0; for (i 0; i ROW; i) { for (j 0; j COL; j) { scanf(%d, a[i][j]); } } for (i 0; i ROW; i) { maxj 0; for (j 1; j COL; j) { if (a[i][j] a[i][maxj]) { maxj j; } } int isMin 1; for (k 0; k ROW; k) { if (a[k][maxj] a[i][maxj]) { isMin 0; break; } } if (isMin) { printf(a[%d][%d] %d\n, i 1, maxj 1, a[i][maxj]); found 1; break; } } if (!found) { printf(not found\n); } return 0; }注意我输出的是i 1和maxj 1因为题目通常要求输出“第几行第几列”下标从1开始而C语言数组下标从0开始。如果题目要求按下标输出你自己调整就行但一定要看清题目。3. 我把这段代码放进编译器之后三个真实踩坑的完整排查过程3.1 坑一列验证只查了下半部分上半行全被漏掉我最初写列验证时直觉以为“验证列最小”只需要从当前行的下一行开始往下比于是写成了这样for (k i 1; k ROW; k) { if (a[k][maxj] a[i][maxj]) { isMin 0; break; } }看起来没什么问题对吧但复盘一下如果要证明a[i][maxj]是整列最小你必须和这一列的所有元素比较包括它上面的第0行到第i-1行。我只比较了下面的行等于默认“上面的元素都比它大”这个默认没有任何依据。举个例子假设第3行的某个元素是候选鞍点它下面的所有元素都大于它但第0行有一个元素比它小那它就不是列最小。我的错误代码会认为它是鞍点输出错误答案。这个坑的教训是在验证类的循环里除非题目明确限制了比较范围否则“遍历所有行”和“遍历部分行”的差别就是正确和错误的差别。老老实实让k从0开始。3.2 坑二标志位没有在每行重置第一行没找到后面全乱第二个坑属于典型的“状态残留”问题。我把isMin这个变量定义在了外层行的循环外面然后在行循环里直接拿来用。int isMin 1; for (i 0; i ROW; i) { // 找maxj... for (k 0; k ROW; k) { if (a[k][maxj] a[i][maxj]) { isMin 0; break; } } if (isMin) { // 输出鞍点 } }第一行验证失败后isMin被置为0。到了第二行isMin仍然是0即使第二行真的有鞍点isMin在进入验证循环前已经是0验证循环里又找不到比它小的元素isMin不会被重新置为1最终就漏掉了正确答案。正确的做法是在每一行开始验证之前把isMin重新赋值为1。也就是放在行循环内部。如果用的是我第一版的写法把int isMin 1;放在外层for循环内部、find maxj之后就不会有这个坑。这个“标志位在每次新循环开始时要重置”的问题在你以后写“判断一组数据是否满足条件”时几乎必然遇到最好一次性记牢。3.3 坑三输出坐标差1第三个坑比较隐蔽也和审题有关。题目如果要求输出“第2行第3列”这里说的是序号从1开始数而不是C语言的下标。C语言里a[2][3]指的是第3行第4列差一位。我当时输出时直接打印了数组下标printf(a[%d][%d] %d\n, i, maxj, a[i][maxj]);如果用下标i和maxj输出和题目要求的位置编号就会差1。更麻烦的是如果你在验证鞍点时用的是a[i][maxj]然后输出i1、maxj1但在检查答案时又下意识用数组下标去对应就会发现“咦怎么跟我的手工推算对不上”。这个不是算法问题是输出格式和坐标系的约定问题。建议在代码里加一行注释提醒自己“i表示行下标输出位置时要加1”。3.4 用printf打断点三步定位问题如果代码有问题且你没有调试器最朴素也最有效的办法就是临时往代码里加printf把中间过程打出来。第一步在找出每行的maxj之后打印一下当前的i和maxj确认行最大值找得对不对。比如printf(debug: row %d, maxj %d, value %d\n, i, maxj, a[i][maxj]);第二步在列验证循环里把每一次比较的两个值打出来printf(debug: compare a[%d][%d]%d with a[%d][%d]%d\n, k, maxj, a[k][maxj], i, maxj, a[i][maxj]);第三步在输出not found的位置打印一下found的最终值。这样你就能定位到是找最大值错了还是列验证的条件写错了还是根本没进入if分支。我靠这个方法短时间内排掉了上面三个坑。等你用过一两轮gdb之后会发现printf调试虽然原始但很多时候定位逻辑错误反而更快因为你能直接看到数据是怎么流动的。4. 边界情况逐个过相等值、多个鞍点、无鞍点与not found输出4.1 相等值严格大于和大于等于的选择标准代码里找行最大值用的是if (a[i][j] a[i][maxj]) { maxj j; }这里用的是严格大于也就是说如果这一行有两个并列的最大值代码只会保留最早遇到的那个。大多数情况下这没问题因为题目通常只要求输出一个鞍点。但有一个边界值得思考如果第一个最大值位置不满足“列最小”而第二个最大值位置满足严格大于的写法会漏掉第二个位置。这种情况在标准测试用例里一般不会出现但作为一种思维训练你可以改用“先记录行最大值然后对每个元素单独判断”的方式保证所有候选位置都被检查到。4.2 多个鞍点输出第一个还是输出所有5x5的矩阵里可能出现多个鞍点。比如矩阵的某几行完全相同每一行都有同一个位置是鞍点这时你break的位置就决定了输出第几个。如果你希望输出第一个找到的鞍点在验证通过后立即break并且把found置为1这是最常见的需求。如果你希望输出所有鞍点就不能break而是要继续扫描每一行把所有满足条件的元素都打印出来。这两种需求的差异不仅仅是break的位置还关系到标志位的使用。输出所有鞍点时found仍然需要存在最后如果一次都没找到还是得输出not found。所以“找所有”不是简单删掉break就行你要保证输出not found的逻辑不被漏掉。4.3 not found的判定位置not found的输出一定要放在整个外层行循环结束之后根据found标志位判断。不能放在行循环内部否则你只检查了几行就提前下结论。这是我见过最常见的错误之一for (i 0; i ROW; i) { // 找maxj、验证列最小 if (!isMin) { printf(not found\n); // 错误应该继续检查下一行 } }如果第0行没有鞍点这个代码就直接输出not found了根本不会去检查第1行到第4行。正确做法是完整跑完所有行用found记录是否找到最后统一判断。4.4 几组可以直接拿去验证的测试数据我整理了几组测试用例覆盖了有鞍点、无鞍点、全相等和负数等场景你可以直接复制到程序里跑用来验证自己的代码测试场景输入矩阵预期输出普通鞍点1 2 3 4 5 / 2 3 4 5 6 / 3 4 5 6 7 / 4 5 6 7 8 / 5 6 7 8 9a[1][5] 5无鞍点1 2 3 4 5 / 2 3 4 5 1 / 3 4 5 1 2 / 4 5 1 2 3 / 5 1 2 3 4not found全等矩阵7 7 7 7 7五行相同a[1][1] 7严格大于时输出第一个负数矩阵-1 -2 -3 -4 -5 / -2 -3 -4 -5 -6 / -3 -4 -5 -6 -7 / -4 -5 -6 -7 -8 / -5 -6 -7 -8 -9a[5][1] -5负数矩阵这组数据特别能检验你是否用了INT_MIN初始化。如果你直接把max初始化为0那么整行的最大值会被错误地判定为0导致结果完全错误。5. 做完题目之后我建议你再走三步扩展、封装、反推5.1 从固定5x5改成m行n列练习17能跑通之后第一件值得做的事就是把它泛化成m行n列。把宏改成两个不等的数字比如ROW3、COL4然后重新录入和验证。如果你用的是C99标准可以直接用变长数组int m, n; scanf(%d %d, m, n); int a[m][n];但很多教材和OJ环境还停留在C89不支持变长数组。这时候要么用宏定义固定尺寸要么用malloc动态分配。对初学者我建议先别急着上malloc把宏定义改成预设的最大尺寸然后只用前m行前n列这样代码改动最小也足够理解m行n列和固定5x5的区别。如果确实想用malloc要注意它是二级指针int **a (int **)malloc(m * sizeof(int *)); for (i 0; i m; i) { a[i] (int *)malloc(n * sizeof(int)); }用完记得逐个free。这块内容对初学者来说是个分水岭能理解则理解理解不了先放一放不影响练习17本身。5.2 把查找逻辑抽成独立函数第二个进阶方向是把查找鞍点的逻辑封装成函数这样主函数会非常清爽。C语言二维数组作为函数参数传参时有一个容易踩的坑函数形参必须指定列数。int findSaddle(int a[][MAXN], int m, int n, int *row, int *col)或者写成指针形式int findSaddle(int (*a)[MAXN], int m, int n, int *row, int *col)为什么必须要指定列数因为二维数组在内存里按行优先存储a[i][j]的地址计算依赖于每一行有多少个元素。如果函数不知道列数它算不出a[i][j]的真实地址。这跟一维数组不同一维数组传参时只需要首地址就能遍历二维数组不行。函数的返回值可以设计成int1表示找到0表示没找到找到的位置通过指针参数row和col带回主函数。这样代码结构清晰也方便以后移植到其他项目里。5.3 找所有鞍点的遍历式写法如果你想把所有鞍点都找出来而不是只输出第一个有一个更直观的写法对矩阵里的每个元素分别检查它是不是行最大、是不是列最小。虽然时间复杂度高一些但逻辑最不容易漏。for (i 0; i ROW; i) { for (j 0; j COL; j) { int isRowMax 1; for (k 0; k COL; k) { if (a[i][k] a[i][j]) { isRowMax 0; break; } } int isColMin 1; for (k 0; k ROW; k) { if (a[k][j] a[i][j]) { isColMin 0; break; } } if (isRowMax isColMin) { printf(a[%d][%d] %d\n, i 1, j 1, a[i][j]); found 1; } } }这种写法和前面的“先按行找候选再验证”相比代码量差不多但每个元素都被独立检查了两遍遇到相等值、多个最大值并列的情况也不会漏。它唯一的缺点是在5x5这种小规模下无所谓但如果是1000x1000的矩阵三层循环的代价就比较大了。作为初学阶段的思维练习两种写法都值得会。5.4 这一步做完之后我对这道题的真实感受练完练习17我最深的体会是C语言里真正难的不是语法而是时刻保持头脑里有两个坐标系——数组下标从0开始生活里的“第几个”从1开始外层循环是行遍历时内层循环的边界和下标交换必须清清楚楚。回头看我第一版代码的问题没有一个是C语言语法不会全是行列下标和边界条件没想清楚。这也是为什么我觉得练习17适合安排在接触二维数组之后不久——它不需要你掌握多高深的算法但逼你把二维数组的两个维度彻底想明白。如果你在练这道题的时候卡住了我建议你先别急着看答案按我说的方法去用printf逐步打印中间结果看到数据怎么流动问题自然就浮出来了。等代码跑通了再顺手把m行n列、函数封装、找所有鞍点这三个扩展练习做一遍你会发现自己对二维数组的理解会上一个台阶。