1. 练习50的题目原貌与鞍点概念的误区1.1 C经典100例里这一题考的是什么《C语言经典100例》的练习50题目原文大致是输入一个5x5的矩阵找出其中的鞍点。所谓鞍点就是该位置上的元素在它所在的行上最大同时在它所在的列上最小最后输出鞍点的位置和值。如果不存在鞍点也要给出相应提示。这题在菜鸟教程的练习序列里属于数组逻辑综合的典型代表前面几十题大多在练指针、练循环、练递归到这一题开始让你把多个知识点串起来用。很多初学者写这题会卡住不是因为语法不熟而是因为既要管行、又要管列的双重条件经常把人绕晕。我自己带过一些学弟学妹他们普遍在先找行最大值还是先找列最小值这个顺序上犹豫很久写出来的代码要么逻辑重复要么干脆漏掉了某一种情况。其实剥开来看鞍点问题考的只有三件事二维数组的元素定位、循环嵌套的边界控制、以及先局部极值再全局校验的算法思路。这三点在后面的链表、排序、图形输出题目里都会反复用到所以说它是承上启下的一道题并不夸张。1.2 鞍点的准确定义与两种常见混淆先把这个定义钉死。教材里鞍点的标准定义是在一个M行N列的矩阵中某个元素a[i][j]满足两个条件第一它是第i行所有元素中的最大值第二它是第j列所有元素中的最小值。换句话说这个元素横着看是老大竖着看是垫底在矩阵的立体图像里它的形状就像一个马鞍的中间点鞍点这个名字就是这么来的。这里有个特别容易混淆的点很多参考书上讲的鞍点是行最大列最小但也有练习题把它写成行最小列最大。两种定义在算法结构上是对称的代码只需要把大于小于号反过来就行。问题在于你考试或者做练习的时候必须先看清楚题目怎么描述我见过好几个同学把列最小写成了列最大结果矩阵里明明有鞍点却提示不存在。我的习惯是拿到题目先把这个条件用注释写死在代码头部比如/* * 鞍点定义a[i][j]是第i行的最大值同时是第j列的最小值 * 如果题目定义相反只需交换 max 和 min 的判断方向 */这样即使后面代码写花了至少核心定义不会跑偏。另一种混淆是关于是否只找一个鞍点。经典100例的练习50只要求判断是否存在并输出一个鞍点因为一个5x5的小矩阵里通常最多只有一个鞍点。但如果你把题目扩展到一般矩阵严格来说可能出现多个鞍点吗答案是可以的。举个极端的例子全0矩阵每一个元素既是行最大又是列最小整个矩阵所有点都是鞍点。标准算法如果只找第一个输出结果本身没问题但如果题目要求输出所有鞍点那就要改成穷举式校验这一点后面到进阶部分我会详细展开。1.3 5x5固定矩阵背后的出题意图为什么这题非要固定成5x5而不是让你输入M和N我猜出题者的本意是降低输入复杂度让你把精力集中在核心算法上。5x5的数据量很小你可以直接在代码里写死数组维度不必处理动态内存分配这对刚接触二维数组的初学者来说更友好。但这里有一个深层用意容易被忽略5x5的规模恰好可以让三种错误全都暴露出来。第一种是行列搞混第二种是并列极值处理不当第三种是不存在鞍点的边界输出。如果你用一个1x1或者2x2的矩阵做测试很多问题根本测不出来。我建议做题的时候不要只按题目要求输入一组数据而是多准备几组特殊数据一会儿到第四节我会给出具体的验证矩阵清单。另外多说一句固定维度还有个好处是方便你肉眼验算。5x5手算一个鞍点并不难你可以先把答案算出来再拿程序跑一遍去对比。但真到了比赛或工程里没人会给你这么规整的矩阵所以我们在基础版本跑通之后还得把固定5x5这个枷锁拆掉做成通用函数这个放到后面讲。2. 从零写出第一版完整代码先求行最大值再做列校验2.1 用行最大值作为切入点的主循环逻辑鞍点算法的结构可以拆成两部分。第一步逐行扫描找出该行的最大值以及它所在的列号。第二步拿着这个列号去检查那一列看看这个值是不是整列的最小值。如果两个条件都满足它就是鞍点。为什么先找行最大值而不是先找列最小值因为行扫描的外层循环可以直接复用矩阵的行索引i而列校验只是对特定列j做一次遍历逻辑上更自然。反过来也不是不行先按列找最小值再校验行但那样需要先循环j再循环i容易把下标搞混。我建议初学阶段就按行主扫描来写降低出错概率。写代码的时候有个细节要注意记录行最大值不要只记一个值要把值本身和它所在的列号一起记下来。因为校验阶段需要通过列号去访问那一列。很多初学者只把最大值存进变量等到要查列的时候就傻眼了。正确的做法是维护两个变量一个存值一个存列索引。这里我用一个临时数组来保存第i行最大值的列号这样可以避免在嵌套循环里反复声明变量。#include stdio.h #include limits.h #define ROW 5 #define COL 5 int main(void) { int matrix[ROW][COL]; int i, j; printf(请输入5x5矩阵的元素 ); for (i 0; i ROW; i) { for (j 0; j COL; j) { scanf(%d, matrix[i][j]); } } for (i 0; i ROW; i) { int max_val INT_MIN; int max_col 0; for (j 0; j COL; j) { if (matrix[i][j] max_val) { max_val matrix[i][j]; max_col j; } } int is_saddle 1; for (j 0; j ROW; j) { if (matrix[j][max_col] max_val) { is_saddle 0; break; } } if (is_saddle) { printf(鞍点位于第%d行第%d列值为%d , i 1, max_col 1, max_val); return 0; } } printf(该矩阵不存在鞍点 ); return 0; }这里有个很容易忽略的地方就是#include limits.h和INT_MIN的用法。为什么初始化最大值用INT_MIN而不是数字0因为矩阵元素允许出现负数如果全矩阵都是负数用0做初始值就会导致一个比真实最大值更大的假最大值被记录进去。用INT_MIN保证第一轮比较一定能被某个元素覆盖。同样的道理如果校验列最小值初始值应该用INT_MAX。这也是热词里stdio.h和limits.h直接相关的一个考点。2.2 列最小值的二次校验怎么设计第二步的校验逻辑我上面代码里用的是is_saddle这个标志位。先假设当前候选点就是鞍点然后去列方向遍历所有行只要遇到一个比max_val更小的值就说明它不是整列的最小值立刻把标志位改成0并跳出循环。is_saddle这个名字是故意的它比flag这种命名更容易读懂。代码可读性在练习阶段就开始培养很重要后面写项目的时候变量名就是给别人看的文档。还有一个小细节校验列的时候内层循环的终止条件是j ROW而不是j COL因为我们要遍历的是5行。这个ROW和COL一旦搞混数组越界和逻辑错误都会来而且编译器不一定会报错只能靠调试查半天。第一版代码从头到尾没有用函数全部摊在main里。这是刻意为之的。初学者阶段先把主线跑通不要急着拆函数拆函数的前提是你对数据流已经非常清楚。如果一上来就封装两个函数来回传矩阵指针反而把二维数组和指针的复杂度叠加到鞍点逻辑上容易劝退自己。2.3 第一版代码的编译验证与样例运行写完之后找一个任意编译器去验证。我一般在本地用 GCC 直接编译gcc saddle_point.c -o saddle_point ./saddle_point用一个最简单的样例比如让第一行的最大值同时是列最小值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这个矩阵里a[0][4] 5是第一行的最大值同时是第5列的最小值所以程序应该输出鞍点位于第1行第5列值为5。如果你运行出来是这个结果说明主逻辑基本没问题。这里的核心验证点是它没有误报其他位置也没有漏掉这个唯一鞍点。建议你亲手算一遍确认程序的输出是对的这个人肉对比的过程能帮你建立对代码的信任感。3. 运行结果与边界条件并列极值、无鞍点、输入残留3.1 行内并列最大值最经典的误判陷阱先把最常见的翻车现场摆出来。假设输入这个矩阵1 2 3 3 5 6 7 8 9 1 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8注意第一行有两个3也就是说第一行的最大值本应是5在a[0][4]没问题。但假如我们换个矩阵1 5 3 5 2 6 7 8 9 1 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8第一行最大值是5但5同时出现在第2列和第4列。按照上面那段代码只会记录第一次出现的列号也就是max_col 1。然后校验第2列发现a[1][1] 7比5大列方向不是最小值于是判定第一行没有鞍点跳到下一行。可实际上第4列里a[1][4] 1、a[2][4] 7、a[3][4] 3、a[4][4] 8这些都比5小吗不是5在第4列依然不是最小值所以这个矩阵确实没有鞍点程序结论碰巧是对的。但再来一个真正的并列陷阱5 3 5 1 2 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3第一行最大值5出现在第1列和第3列。程序只检查第1列发现a[1][0] 1 5不是列最小值就判定第一行没有鞍点。可是第3列呢a[1][2] 3、a[2][2] 4、a[3][2] 5、a[4][2] 1这里有4、5都比5小吗没有实际上 5 在第3列中并不是最值等等第3列的值分别是5、3、4、5、1最小值是1所以5也不是列最小值。那这个矩阵有鞍点吗我们继续看后面行。第二行最大值是5在第5列第5列值是2、5、1、2、3最小是1也不是。第三行最大值是5在第4列第4列值是1、4、1、1、3最小是1也不是。第四行最大值是5在第3列已经看过了。第五行最大值是5在第1列已经看过了。结论确实没有鞍点。好那我的例子没构造好我们直接构造一个真正有并列最大且第二个位置是鞍点的矩阵。5 2 5 1 0 1 9 2 3 4 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8第一行最大值是5出现在第1列和第3列。程序只查第1列第1列的值是5、1、2、3、4最小是1所以5不是列最小值被判定为无鞍点并跳过。但看第3列值是5、2、4、5、6最小值是25也不是列最小值。意不意外这里依然没有鞍点。我自己手滑了换个真能命中的5 3 1 4 2 1 9 8 7 6 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8第一行最大值5出现在第1列第1列值是5、1、2、3、4最小是1不满足。第3列值是1、8、4、5、6最小是15也不满足。还是不行。真正要命中需要并列最大值中的一个位置它的列方向恰好比所有同列值都小另一个位置列方向不满足。比如6 3 6 1 2 7 8 9 4 5 1 2 3 5 6 2 3 4 6 7 3 4 5 7 8第一行最大值6出现在第1列和第3列。第1列值是6、7、1、2、3最小值是16不是列最小。第3列值是6、9、3、4、5最小值是36也不是列最小。还是没有。看第二行最大值9在第3列第3列最小值39不满足。第三行最大值6在第5列第5列值是2、5、6、7、8最小26不满足。第四行最大值7在第4列和第5列第4列值1、4、5、6、7最小值17不满足第5列也已看过。第五行最大值8在第5列不满足。这个矩阵没有鞍点。构造鞍点矩阵比我想象中难这是有原因的——稍后我会解释为什么大多数随机矩阵都没有鞍点。算了不硬凑了。我直接用一个简单的有并列最大值且真鞍点在第二个位置的矩阵4 2 2 1 0 2 3 4 5 6 1 2 3 4 5 3 4 5 6 7 2 3 4 5 8第一行最大值4只在第1列没有并列。我说了构造这种例子确实费劲但原理是清楚的只要行内有两个地方都是最大值而你的代码只记录第一个那么真正满足列最小条件的第二个位置就会被漏掉。解决思路有两种一是把所有行最大值列号都存进一个数组然后逐个去校验列二是遇到并列最大值时全部记录不急着覆盖。标准做法是开一个一维数组max_cols[COL]同时用一个计数器cnt记录本行有哪些列达到了最大值然后对这cnt个候选位置逐一校验。根据我的实际经验菜鸟教程的原题测试数据里几乎不会出现第二个并列最大值才是鞍点这种变态情况所以第一版代码能应付绝大多数验证。但如果你想举一反三或者后面真的做通用矩阵工具这个坑必须提前补上。我会在第五节的通用版本里给出支持全部候选点的解法。3.2 矩阵不存在鞍点时程序怎么反馈练习50原题没有硬性规定无鞍点时输出什么但按一般OJ在线评测系统的习惯输出不存在或No saddle point都算对。我第一版代码用的中文提示实际OJ会要求精确的英文输出比如No saddle point。自己练习当然无所谓但如果你是为了应付考试或刷题网站输出格式一定要看清楚少一个换行符都可能被判错。这里牵出一个值得养成的习惯程序要有找不到结果时该怎么办的显式分支。很多人写循环找东西找到就打印、找不到就什么都不打印这在练习里可能不被扣分但在真实工具里是灾难——用户不知道程序到底跑完了没有。我的习惯是永远写一个兜底输出就像上面的printf(该矩阵不存在鞍点 );这行代码看起来不起眼但它保证了程序在任意输入下都有明确的输出可测试性大大提升。3.3 输入层的问题scanf的换行与缓冲区残留写这题还有一个几乎必踩的坑scanf读取整数时会跳过空白字符所以下面这种逐行输入方式本身没问题1 2 3 4 5 6 7 8 9 10 ...就算你每行末尾多打了空格scanf(%d)也会自动跳过。真正有问题的是混合输入。比如你在程序前面先读了一个字符或者字符串缓冲区里残留了换行符后面的scanf(%d)并不会受影响因为%d天生跳过空白。受影响的场景是scanf(%c)读取单个字符它会把换行符吃进去。鞍点这题全是纯整数输入理论上不太会遇到输入残留的坑。但有一个细节值得一提如果用户输入了非数字字符比如ascanf会返回0并保持缓冲区内字符不动程序随后可能陷入死循环或者读取到垃圾值。严谨一点的写法是检查scanf的返回值if (scanf(%d, matrix[i][j]) ! 1) { printf(输入格式错误 ); return 1; }这在刷题网站里无所谓但放到真实项目中就是一种最基本的防御性编程。我建议你在练习阶段就养成检查返回值或至少检查关键输入的习惯后面读取文件、接收网络数据都会用到同样的思路。4. 调试与排查用测试矩阵矩阵验证算法正确性4.1 五个必测的特殊矩阵写完代码先别急着提交拿下面五组数据去验证。我在带人练这题的时候只要这五组能全过逻辑上基本就稳了。第一组标准鞍点矩阵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预期输出第1行第5列值5。第二组无鞍点矩阵1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 5 6 7 8 8我把右下角改成了8原来每一行的最大值都出现在最后一列但现在最后一列里a[4][4] 8比a[0][4] 5大第一行的5不是列最小值其他行更不可能预期输出不存在鞍点。第三组全相同矩阵3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3按严格定义每个元素既是行最大又是列最小所以存在大量鞍点。第一版代码只会输出第一个但输出本身没有错。这里主要验证程序不会崩溃。第四组负值矩阵-5 -4 -3 -2 -1 -4 -3 -2 -1 0 -3 -2 -1 0 1 -2 -1 0 1 2 -1 0 1 2 3第一行最大值是-1在第5列第5列是所有行里最大的不是列最小所以没有鞍点。这个矩阵验证的是INT_MIN初始化是否正确。如果你用0做初始值这里会误判。第五组递增对角矩阵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等等这个和第一组一样。换一个单元素敏感矩阵1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25这个矩阵每个元素都行最大值在最后一列但最后一列也是递增的最小值是5在第一行a[0][4]5恰好是第一行最大值且是第一列不对是第一行最大值是5第5列最小值也是5所以唯一的鞍点是a[0][4] 5。用这个矩阵验证程序能不能找到最大值同时在最后一列的情况。这五组数据覆盖了正常命中、完全没有鞍点、全等极端、负数、单调递增五种典型场景。其中第三组能暴露只找第一个的局限性第四组能暴露INT_MIN的重要性。建议你把它们写成一个临时文件一遍遍跑输出和预期一致之后再继续往下做。4.2 把验证逻辑写成一段自检代码手工输入五组矩阵很累而且容易敲错。我在练习时有个小习惯把测试数据直接写死在代码里用宏切换或注释切换。比如把矩阵定义改成#ifdef TEST_MODE int matrix[ROW][COL] { {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} }; #else // 手动输入 #endif用 GCC 编译时加-DTEST_MODE即可切换到固定测试数据。这样改一组数据重新编译一次效率比每次手工敲键盘高得多。而且在调试阶段固定输入能保证问题必现你不需要怀疑自己上一次是不是把数字输错了。如果你想让自检更进一步可以写一个check(int matrix[ROW][COL])函数用暴力穷举法做基准遍历每个元素检查它是否是行最大且列最小把所有鞍点都收集起来。然后用这个暴力版本和你的高效版本对比结果。暴力版本虽然慢但逻辑极其简单几乎不会写错是天然的参考答案。我在做算法重构时经常用这种暴力版优化版对照的方法能省下大量调试时间。void check_all_saddles(int matrix[ROW][COL]) { int i, j, k; int found 0; for (i 0; i ROW; i) { for (j 0; j COL; j) { int is_row_max 1, is_col_min 1; for (k 0; k COL; k) { if (matrix[i][k] matrix[i][j]) { is_row_max 0; break; } } for (k 0; k ROW; k) { if (matrix[k][j] matrix[i][j]) { is_col_min 0; break; } } if (is_row_max is_col_min) { printf(候选鞍点(%d, %d) 值%d , i 1, j 1, matrix[i][j]); found 1; } } } if (!found) { printf(无鞍点 ); } }注意这个暴力版里行最大用的条件是如果遇到相等元素它不会阻止当前元素成为行最大因为严格大于才刷新等于不算击败。这样全等矩阵就会输出所有25个位置。这个行为和第一节说的定义完全一致可以作为标准答案去比对。4.3 稳定性与可读性的取舍为什么不要急着炫技第一版代码完全可以用但有些读者可能会觉得它不够高级。网上搜这题你能看到各种变体用函数指针、用动态二维数组、用结构体存坐标。我建议你先别急着模仿。菜鸟教程练习50的核心价值是把基础走稳如果你一上来就把代码拆成五个函数加三个结构体调试难度会直线上升。等你能闭着眼写出第一版之后再去考虑怎么让它更通用、更健壮。这个顺序很重要。我见过太多初学者代码写得特别花哨结果一个空指针解引用就崩了反而没法跑出正确结果。代码首先是给人看的其次是给机器跑的。在练习阶段能读懂、能改对比看起来厉害重要得多。5. 进阶从固定5x5到通用矩阵与真实场景5.1 封装成支持任意MxN矩阵的通用函数题目做完之后可以试着把维度参数化。最自然的方式是把算法抽成函数接收行数、列数和矩阵数据。在C语言里二维数组传参有个麻烦函数参数必须指定列数或者退化成指针。一般进阶做法是这样int find_saddle_point(int rows, int cols, int matrix[rows][cols]) { int i, j; int found 0; for (i 0; i rows; i) { int max_val INT_MIN; int candidate_cols[COL_MAX]; // 记录本行所有最大值的列 int cnt 0; for (j 0; j cols; j) { if (matrix[i][j] max_val) { max_val matrix[i][j]; cnt 0; candidate_cols[cnt] j; } else if (matrix[i][j] max_val) { candidate_cols[cnt] j; } } int k; for (k 0; k cnt; k) { int col candidate_cols[k]; int is_col_min 1; for (j 0; j rows; j) { if (matrix[j][col] max_val) { is_col_min 0; break; } } if (is_col_min) { printf(鞍点第%d行第%d列值%d , i 1, col 1, max_val); found 1; } } } return found; }注意我在处理并列最大值时用了candidate_cols数组里面存的是该行所有达到最大值的列号。这是对3.1节那个坑的正式修复。if-else分支的顺序很关键先是严格大于刷新最大值并重置候选列表然后是等于追加进候选列表。这样即使一行有多个最大值也不会漏掉任何一个候选位置。不过这个版本的COL_MAX还是个固定上限真要支持任意大小的矩阵得用动态内存。更工程化的做法是把矩阵拍平成一维数组用matrix[i * cols j]去访问元素。这样传参就只有一个int *加行列数不涉及变长数组的兼容性问题。很多嵌入式项目里二维数组其实就是这么访问的因为底层内存本来就是线性的。5.2 性能分析与还能优化的角度先算一下复杂度。我上面介绍的行扫描列校验算法外层遍历每一行内层先扫所有列找最大值再扫所有行校验列所以最坏时间复杂度是 O(rows * (cols rows))。对于5x5这种规模根本没区别但放到1000x1000的矩阵里性能差距就出来了。有一种优化策略是先把每行的最大值和每列的最小值预处理成两个一维数组比如row_max[i]和col_min[j]然后只需要一次双重循环检查matrix[i][j] row_max[i] matrix[i][j] col_min[j]复杂度降到 O(rows * cols)。这个思路在面试里经常被拿出来聊因为它展示了你对空间换时间的理解。实现并不难关键是要同时维护两个辅助数组int row_max[ROW], col_min[COL]; for (i 0; i ROW; i) { row_max[i] INT_MIN; for (j 0; j COL; j) { if (matrix[i][j] row_max[i]) row_max[i] matrix[i][j]; } } for (j 0; j COL; j) { col_min[j] INT_MAX; for (i 0; i ROW; i) { if (matrix[i][j] col_min[j]) col_min[j] matrix[i][j]; } }然后再遍历一遍矩阵把所有同时满足两个等式的坐标全部输出。这个版本的代码量反而更少逻辑也更清晰。唯一的缺点是多了两个数组的内存但对于矩阵求鞍点这种场景空间几乎不是瓶颈。还有一个优化角度值得提关于全等矩阵的特殊情况。当矩阵所有元素都相等时按定义所有位置都是鞍点这句话在某些OJ里可能不被认可因为有的题目会额外规定鞍点必须严格大于行内其他元素且严格小于列内其他元素。如果题目有严格二字那你遇到全等矩阵时程序要输出不存在。判断方法很简单检查row_max[i] col_min[i]时还不算完必须确认这个值在行内是唯一的。这一点在阅读原题时要特别小心选择大于等于还是严格大于会让结论完全不同。5.3 鞍点概念在真实项目里的应用参考学完这题你可能会想这东西除了考试还有啥用其实鞍点这个概念在很多领域都有对应。地形分析里鞍部是两个山峰之间的低洼处能用于判断地形走势图像处理里检测灰度图的局部极值点类似这个思路只是把二维数组换成了像素矩阵博弈论里的鞍点则对应最坏情况下的最优策略那里的算法就复杂得多了。在C语言工程里鞍点问题的价值主要是训练一种思维模式先求局部特征再做全局交叉验证。这种模式在很多数据处理场景中都会复现。比如你有一张销售表格想知道哪个产品在某个区域销量最高同时这个区域整体销量最低本质上就是一个带条件的行列极值匹配。把矩阵的维度换成时间序列和产品类型你就能设计出一个简单的一维数组版鞍点分析工具。我早期做报表工具时写过类似的逻辑当年如果先做过这道练习大概能少加两天班。顺着这个思路可以继续扩展的方向很多换成一维数组做局部峰值检测改成链表存储矩阵来省内存甚至结合多线程把行列扫描并行化。但这些都是后话了先把练习50吃透后面的路自然就顺了。我个人做这题最大的体会是别小看这些经典100例里的老题目。它们的难度不高但每一个都精准地踩在语言特性和算法思维的结合点上。鞍点这题尤其体现了先拆解条件、再设计流程、最后处理边界的完整套路。把这个套路练成肌肉记忆比多背十个语法细节都管用。
