在菜鸟教程的C语言经典100例里练习67算是一道分水岭。前面几十题还在跟变量、循环、一维数组打交道到了这一题二维数组刚讲完题目就上来了输入一个5x5矩阵找出矩阵中的鞍点。啥是鞍点就是某个元素在它所在的那一行里是最大值在它所在的那一列里又是最小值。题目一句话就能说清真下手写代码时很多人却卡在同一个地方——怎么同时证明一个元素既符合行的条件又符合列的条件。这篇文章把我刷这一题的完整思路、写出来的两套实现、以及调试中踩过的坑都梳理一遍给同样卡在这里的你做个参考。1. 练习67到底考什么鞍点背后的二维数组基本功1.1 鞍点的定义先把它翻译成人话先别急着写代码把题目翻译成人话给你一张5行5列的表格你要在里面找一个格子这个格子要满足两个条件——它比同行的其他4个数都大同时又比同列的另外4个数都小。这两个条件缺一不可。有的教材也把行最小、列最大叫做鞍点定义方向正好反过来。这题的约定是行最大、列最小。我的建议是不管做题还是面试动手前先确认定义方向不然整个代码逻辑就要对称反过来写很容易白忙一场。鞍点这个名字可以这样理解就像马鞍沿马背的方向看你处在最高点沿马腹横切的方向看你又处在最低点。一个元素在行和列两个方向上高低不一致数学上就叫鞍点。我第一次见这个词的时候觉得挺抽象后来在纸上画了个马鞍的侧视图一下就懂了。1.2 这一题的位置为什么是二维数组的分水岭菜鸟教程的经典100例前面大量题目都在训练单一方向的遍历求数组和、找最大值、逆序输出……一次循环搞定。练习67第一次要求你从两个方向看同一个元素。这意味着二维数组的存储方式你得真正理解a[i][j]在内存里是按行连续存放的但逻辑上你随时可以按列取数。找行的最大值你是顺着某一行走验证列的条件你又要顺着某一列走。两种扫描方式在同一个题目里交叉出现脑子里得有一张行列交叉的图景才行。题目固定为5x5而不是任意行列也是教学上的有意安排行数和列数都可以用宏定义代码里到处是ROW、COL可读性比裸写5好很多也方便以后改成通用形式。实际上等你自己把这道题改成M行N列之后你会发现自己对二维数组下标的敏感度提升了一个档次。1.3 头文件怎么选stdio.h和limits.h各自的用途头文件方面stdio.h是雷打不动的scanf和printf都靠它。真正容易让人疑惑的是limits.h很多参考答案里都写着#include limits.h但没人解释为什么。原因在于初始化策略当你要找最小值时最稳妥的初始化不是拿a[0][0]当起点而是直接用INT_MAX——int类型能表示的最大值。任何一个真实读入的元素都会比INT_MAX小这样第一次比较必然更新你就不会因为数组第一格恰好是最值之类的情况干扰判断。反过来找最大值就用INT_MIN初始化。这两个常量就定义在limits.h里。当然用a[0][0]或a[i][0]这种第一个元素来初始化也没错5x5矩阵里第一格一定存在而且还能省一个头文件。到底选哪种我给一张对比表初始化方式依赖头文件优点需要注意的地方用a[0][0]等实际元素只需要stdio.h语义贴近矩阵本身不使用极限值概念要求数组至少有一个元素空数组场景下会出错用INT_MAX / INT_MIN需要limits.h不依赖输入数据逻辑统一适合通用代码新手容易忽略int类型极限值的概念两种都没错。我的看法是学习阶段把两种写法都敲一遍理解它们各自的适用场景和价值比死记某一种写法有用得多。2. 核心思路拆解为什么先求行最大再验列最小最稳2.1 从定义出发一个元素需要过两关把条件拆开看a[i][j]是鞍点需要同时满足两个等式a[i][j]等于第i行的最大值并且a[i][j]等于第j列的最小值。注意这里用的是等于而不是大于或小于。因为最大值和最小值是具体的数拿这个数跟当前元素比较判别即可。于是一个很自然的做法浮现出来先找每一行的最大值注意不是只找数还要记住它所在的列然后拿着这个行最大的位置到那一列里做一次最小值验证。如果列最小值恰好也等于它说明这个位置同时满足两个条件鞍点找到了。这个思路的关键点在于找行最大值时要同步记录列下标否则第二遍扫描不知道去哪一列验证。很多初版代码没记住列号验证时只能在整行里瞎转最后结果自然不对。把数值和位置绑定在一起记录是这类题目的通用技巧。2.2 两套写法的设计对比即时验证版与预处理数组版顺着上面的思路代码写法可以分成两派。第一派叫即时验证外层循环每扫一行就把这一行的最大值找出来定位到列紧接着去该列扫一遍确认是否最小输出完再进入下一行。这派省内存思路直接。第二派叫预处理数组先扫所有行把每行的最大值存进row_max[5]再扫所有列把每列的最小值存进col_min[5]最后双层循环遍历每个格子只要它同时等于row_max[i]和col_min[j]就是鞍点。两派都能解决这道题我推荐后者。理由有三个。第一逻辑三段式每一段的职责单一出错了容易定位。第二第三遍遍历天然能输出全部鞍点而即时验证版在一行有多个并列最大值时可能漏判。第三它更容易改造成任意行列的通用代码。下面这张表格对比得更清楚对比维度即时验证版预处理数组版额外空间不需要两个长度5的一维数组逻辑复杂度两层循环嵌套代码较短三段循环层次更清晰一行出现多个并列最大值可能漏判不会漏判扩展为任意行列需要小心改写比较自然代码可读性中等较好2.3 时间复杂度和空间复杂度这笔账关于复杂度简单算一笔账。即时验证版对每一行找最大值要比较4次5行就是20次对每一行的最大值去对应列验证又比较4次5行又是20次总共约40次比较。预处理数组版第一遍5行各4次第二遍5列各4次第三遍25个格子逐一判断合计也是几十次的量级。两者都是O(n²)的复杂度在5x5的规模下差别完全可以忽略。所以不要为了省几个字节的数组空间在5x5这样的小规模题目里抠性能。把逻辑写对、写清楚这道题才算真正学会了。等你以后处理真正的大矩阵优化方向也绝不是这种常数级的改动而是从算法思路上换方案。3. 代码实现与运行实测两套方案的完整对比3.1 方案一行最大即时验证版先看即时验证版完整代码如下#include stdio.h #define ROW 5 #define COL 5 int main(void) { int a[ROW][COL]; int i, j, k; int found 0; printf(请输入5x5矩阵的元素共25个整数\n); for (i 0; i ROW; i) { for (j 0; j COL; j) { scanf(%d, a[i][j]); } } for (i 0; i ROW; i) { int row_max a[i][0]; int max_col 0; // 找第i行的最大值并记录所在列 for (j 1; j COL; j) { if (a[i][j] row_max) { row_max a[i][j]; max_col j; } } // 在第max_col列找最小值 int col_min a[0][max_col]; for (k 1; k ROW; k) { if (a[k][max_col] col_min) { col_min a[k][max_col]; } } // 行最大值同时也是该列最小值 if (row_max col_min) { printf(鞍点a[%d][%d] %d\n, i, max_col, row_max); found 1; } } if (!found) { printf(该矩阵不存在鞍点。\n); } return 0; }这段代码里max_col是整段代码的枢纽。它记录着当前行最大值所在的列号第二遍扫描必须靠它找到正确的列。其次是col_min的初始值这里用a[0][max_col]作为起点所以内层循环从k1开始少一次无意义的比较。最后row_max col_min成立说明行最大值同时也是列最小值鞍点就在(i, max_col)处。3.2 方案二预处理数组版也是我推荐的写法预处理数组版代码稍微多几行但逻辑更清晰#include stdio.h #include limits.h #define ROW 5 #define COL 5 int main(void) { int a[ROW][COL]; int row_max[ROW]; int col_min[COL]; int i, j; int found 0; printf(请输入5x5矩阵的元素共25个整数\n); for (i 0; i ROW; i) { for (j 0; j COL; j) { scanf(%d, a[i][j]); } } // 第一遍求每行的最大值 for (i 0; i ROW; i) { int max INT_MIN; for (j 0; j COL; j) { if (a[i][j] max) { max a[i][j]; } } row_max[i] max; } // 第二遍求每列的最小值 for (j 0; j COL; j) { int min INT_MAX; for (i 0; i ROW; i) { if (a[i][j] min) { min a[i][j]; } } col_min[j] min; } // 第三遍遍历所有元素判断是否同时满足两个条件 for (i 0; i ROW; i) { for (j 0; j COL; j) { if (a[i][j] row_max[i] a[i][j] col_min[j]) { printf(鞍点a[%d][%d] %d\n, i, j, a[i][j]); found 1; } } } if (!found) { printf(该矩阵不存在鞍点。\n); } return 0; }这里row_max[i]存放第i行的最大值col_min[j]存放第j列的最小值。初始化时用INT_MIN和INT_MAX正是limits.h的职责所在——任何读入的整数都比INT_MIN大、比INT_MAX小所以第一轮比较一定成立初始值不会干扰结果。第三遍里的核心判断只有一行a[i][j] row_max[i] a[i][j] col_min[j]这句话就是整道题的灵魂。3.3 运行实测有鞍点、无鞍点、多鞍点三种情况用两组数据实测。第一组有鞍点请输入5x5矩阵的元素共25个整数 30 20 10 5 1 40 50 60 70 80 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 鞍点a[0][0] 3030在首行里是最大的同时在第0列里又是最小的所以它是标准的鞍点。第二组无鞍点请输入5x5矩阵的元素共25个整数 9 8 7 6 5 1 2 3 4 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 该矩阵不存在鞍点。这组数据的每行最大值分别出现在不同列但对应的列最小值全都不在那个位置于是没有任何鞍点。程序给出了明确提示而不是安静地结束。还有一种极端情况值得试全相等矩阵比如25个数全是7。那么7就是每行的最大值也是每列的最小值25个格子全是鞍点。用预处理数组版会打印25行输出用即时验证版因为每行只记录第一个max_col只会打印5行。这个例子最能说明两个版本在并列最值处理上的差别。4. 最容易翻车的细节并列最值、无鞍点与边界下标4.1 一行有多个相同最大值时你可能真的会漏判这一节聊聊我实际调试时翻过车的点。最隐蔽的问题是一行里出现多个相同的最大值时即时验证版会漏判。假设第i行最大值是10出现在第0列和第3列第0列的最小值是8不是10而第3列的最小值恰好是10。真正的鞍点在(i, 3)可即时验证版只按max_col记录了先扫到的第0列验证失败后就直接说这一行没有鞍点了完美错过正确答案。要补救也简单找到row_max后再遍历这一行的所有列凡是a[i][j] row_max的都拿去做列最小值验证。伪代码可以这样写for (j 0; j COL; j) { if (a[i][j] ! row_max) { continue; } int col_min a[0][j]; for (k 1; k ROW; k) { if (a[k][j] col_min) { col_min a[k][j]; } } if (col_min row_max) { printf(鞍点a[%d][%d] %d\n, i, j, a[i][j]); found 1; } }我写完之后发现这个补救动作其实已经和方案B的第三遍遍历非常接近了。你看写着写着就绕回了预处理数组版。所以我常说与其在即时验证版上打补丁不如一开始就使用预处理数组版一步到位把逻辑理清。4.2 矩阵没有鞍点时程序不能安静地失败第二个大坑是没有鞍点时程序的表现。很多初版代码只在找到鞍点时打印没找到就什么都不输出。你跑一个矩阵屏幕上一片空白到底是有鞍点没打印出来还是压根没有分不清。所以一定要用一个标志变量found找到任意鞍点就置1整个扫描结束后检查它为0就明确输出一行提示。别小看这一句输出课堂作业和笔试里有没有这句提示直接决定了程序在边界情况下是否完整。这也是一个表达能力的问题——程序不仅要算得对还要把结果交代清楚。4.3 下标和初始化里的经典错误第三个坑是下标相关的问题。常见的是找行最大值时只记了最大值本身把列号落在循环外面变量一重用就出错。更隐蔽的是max_col忘了初始化默认从0开始结果第一行最大值在别处时验证就跑到了错误的列上去。还有比较运算符写反找最大写成了if (a[i][j] max)找最小写成了if (a[k][j] min)跑出来的结果天差地别。这种错误通常不是故意写错而是复制粘贴时没改符号调试时却特别难发现。再一个细节是第二遍扫描的循环起点。用a[0][max_col]做初始值时循环可以从k1开始少一次无意义的比较若用了INT_MAX做初始值循环就必须从0开始因为要保证每个元素都被比较到。这些细节单独拎出来都是小问题但它们恰恰是调试时最磨人的地方。4.4 输入环节的友情提醒最后说输入。scanf(%d, a[i][j])里千万别丢这是初学阶段最高频的报错之一。另外5x5共25个整数推荐每行5个分五组输入回车分隔和矩阵形状对应。一次性全部挤在一行也能跑但万一哪个数据输错了定位起来很难受。想要更稳一点scanf的返回值是成功读取的个数等于1才说明读到了一个整数这个值的检查在练习阶段容易被忽略但等你以后写正规程序输入校验就是基本功了。5. 从练习67延伸出去通用化改造与同类题目的套路5.1 改成任意MxN矩阵其实不难练习67写完后可以顺手做一件事把5x5改成任意M行N列。宏定义换成两个变量rows和cols从标准输入读入再把三个循环的上限全部替换。二维数组如果用变长数组可以直接写int a[rows][cols]如果编译器较老就用malloc动态分配或者固定上限的大数组。关键之处是让所有循环都依赖rows和cols而不是写死在5上。改造后的代码要注意边界情况行列数不能为0为0时应该直接输出无鞍点并返回。这一步改造做完你对下标和循环控制的理解会再上一个台阶。很多学生刷题只满足于跑通当前数据不愿意做这种小重构结果遇到把5改成n的变体题目照样懵。5.2 遇到行最小、列最大的鞍点定义怎么办遇到定义方向反过来的题目也别慌。行最小、列最大跟行最大、列最小之间差的只是一个视角翻转。把原矩阵转置一下原来的列就变成了行原来的行就变成了列行最小列最大就变成了行最大列最小。所以你可以对转置后的矩阵跑同一套代码找到的结果再映射回原下标或者更直接把找最大值时的比较符号换成小于、把找最小值的换成大于。编程题的变体大多都这样换汤不换药。关键在于一开始读懂题目定义的方向不要默认所有鞍点题都是行最大列最小。我见过不止一个同学在面试时因为没确认这点把整个逻辑写反最后又不敢问白白送分。5.3 这类行列交叉判断题目的通用套路把这道题吃透之后你再往后刷会发现很多题目都在用同一套思想先按一个方向扫描把结果记录下来再按另一个方向扫描把两个结果交叉对比。矩阵转置是行列下标交换杨辉三角是斜向递推幻方是行、列、对角线三条线的和做校验思路本质上都是多维扫描加结果归约。练习67其实就是这个套路的最小样本。我给自己的刷题建议很简单拿到题目先别写代码用笔在纸上画一个3x3的小矩阵把行最大列最小手动标一遍然后设计变量记录中间结果最后才动手敲。你会发现绝大多数二维数组题目都可以这样平稳落地。这个习惯比多做十道题都有用。我个人刷完练习67最大的体会是这题并不难难的是把两个方向的条件拆开、分别计算、再合并。能一次想明白这件事后面很多二维数组的题都会顺畅很多。最后分享一个小习惯——写完代码不要急着看答案先拿自己构造的矩阵跑一遍有鞍点、无鞍点、全相等三种情况都试一下这个习惯帮我养成了对边界条件的敏感也让我少踩了很多坑。