1. 鞍点的定义分歧先把判定条件咬死再动手写代码拿到这道题的人十个里有八个第一反应是两层循环再套两层判断三分钟的事。真正动手写才发现第一版代码在课本那个 3×3 小测例上跑得挺欢一提交就 WA或者用随机数据对拍时发现结果少了一个。问题几乎从不出在循环写错而是出在定义根本没吃透。鞍点这个概念属于典型的一句话题面、三种理解的题目。所以我在动手敲键盘之前会强迫自己先回答三个问题判定方向是哪一种、鞍点是否唯一、输出格式要求是什么。这三件事定不下来代码写得再漂亮都是白费。1.1 行最小配列最大还是行最大配列最小最常见的口径是某个元素在它所在的行里是最小的在它所在的列里是最大的那它就是鞍点。但确实有一批教材和题库把它反过来要求行最大、列最小。这两种口径不是同一个东西结果可能完全相反。拿一个最朴素的 3×3 矩阵看1 2 3 4 5 6 7 8 9按行最小 列最大找各行最小值分别是 1、4、7各列最大值分别是 7、8、9。交集只有 7也就是 (2,0) 这个位置它是鞍点。换成行最大 列最小各行最大值是 3、6、9各列最小值是 1、4、7两边完全没有交集一个鞍点都没有。同一个矩阵两种理解给出完全相反的答案。所以看题面的时候最小和最大这两个词分别挂在行还是列上一定要逐字确认。我见过有人抄题的时候把两个词写反然后对着代码 debug 两个小时最后发现是抄错了。1.2 重复元素让唯一性假设直接翻车很多人的代码里藏着一个没写出来的假设每一行的最小值只有一个位置每一列的最大值也只有一个位置。这个假设在数据随机的情况下大概率成立但只要出题人想卡你一组重复数据就能让你从满分掉到一半。看这个两行两列的矩阵2 1 1 1按行最小 列最大来算。第 0 行最小值是 1出现在 (0,1)第 1 行最小值也是 1出现在 (1,0) 和 (1,1)。再看列第 1 列的最大值是 1位置是 (0,1) 和 (1,1)。于是 (0,1) 满足条件(1,1) 也满足条件这个矩阵有两个鞍点。如果你的代码只记录每行第一个最小值的列下标那你就会只拿到 (0,1)把 (1,1) 漏掉。这就是为什么后面三种方法里我都会强调用相等判定而不是位置记录。相等判定天然地把所有重复位置都覆盖进去了位置记录则要求你额外维护一个候选列表。1.3 数据规模决定了你该选哪一种写法三种方法在复杂度上差距巨大但选哪种从来不是看哪个高级而是看题目给的 n 和 m 落在哪个区间。我的经验判断线大致是这样n、m 在 100 以内方法一的三重循环随便写几十毫秒跑完没必要折腾。n、m 到 1000 级别方法一的 2×10⁹ 次操作基本必超时必须上方法二。多组测试数据、每组规模都不小的时候方法二里数组的复用和清零方式会影响常数得留个心眼。题目如果只要求输出任意一个鞍点、而且明确保证唯一那方法二还能再省一层判断。另外提醒一句二维数组开到 1000×1000 的 int 就已经是 4MB 了放在 main 函数内部可能直接爆栈段错误养成把大数组开成全局变量的习惯这个问题会少很多。2. 方法一三重循环暴力判定先能跑通再谈优化2.1 判定逻辑把题面原封不动翻译成代码暴力法的思路没有任何技巧可言它的价值就在于最不容易出错。具体做法是把矩阵里的每一个元素都当成嫌疑人轮流验证两条证据——它是不是所在行的最小值、它是不是所在列的最大值。两条都成立它就是鞍点。这里的验证过程本身就是一次线性扫描。要判断 a[i][j] 是不是第 i 行最小就把第 i 行从头到尾扫一遍只要遇到一个比它小的立刻否定要判断它是不是第 j 列最大就把第 j 列从上到下扫一遍只要遇到一个比它大的立刻否定。这个遇到反例立刻 break的写法很关键。它不是为了炫技而是实实在在地减少常数在随机数据下绝大多数元素在扫描的头几个位置就会被否定掉实际运行时间远低于理论上限。2.2 完整代码与逐行说明#include bits/stdc.h using namespace std; const int MAXN 105; int a[MAXN][MAXN]; int main() { int n, m; while (cin n m) { for (int i 0; i n; i) for (int j 0; j m; j) cin a[i][j]; bool found false; for (int i 0; i n; i) { for (int j 0; j m; j) { bool rowMin true, colMax true; for (int k 0; k m; k) { if (a[i][k] a[i][j]) { rowMin false; break; } } for (int k 0; k n; k) { if (a[k][j] a[i][j]) { colMax false; break; } } if (rowMin colMax) { cout saddle: ( i , j ) a[i][j] \n; found true; } } } if (!found) cout no saddle point\n; } return 0; }几个容易被忽略的细节。第一while (cin n m)这种多组输入写法比只读一组要稳妥因为不少 OJ 题目会在一个文件里塞多组测试数据只读第一组会直接 WA。第二found这个标记必须在每一组数据开头重置否则上一组找到过鞍点这一组就会漏掉 no saddle point 的输出。第三行扫描和列扫描用了同一个循环变量名k但它们的上界一个是m一个是n写反是新手最常见的错误之一建议下意识地检查一遍。2.3 复杂度这笔账以及暴力法的真正用途时间复杂度是 O(n × m × (n m))。代入具体数字感受一下100×100 的矩阵大约是 2×10⁶ 次操作几十毫秒内跑完非常轻松但换成 1000×1000操作次数直接涨到 2×10⁹普通评测机跑这种规模基本是秒级起步超时是必然的。但我不建议你把暴力法当成劣质方案扔掉。它的真正用途是对拍基准。写完更高效的方法二或方法三之后随手生成几百组随机小矩阵两个程序各跑一遍比较输出是否一致这个习惯能帮你在五分钟内定位掉大部分逻辑错误比手动造数据快得多。还有一个实战点暴力法对输出所有鞍点和输出第一个鞍点两种要求都能直接适配因为它是全量扫描遇到就输出。如果你的代码要先跑通再优化那第一版就写它绝对不会错。3. 方法二预存行最小值与列最大值两次遍历收工3.1 空间换时间把重复扫描的结果存下来暴力法慢在哪里慢在每一个元素都要重新扫一遍它所在的行和列。但其实第 i 行的最小值跟你在看第 i 行第几个元素完全没关系。既然这样不如先把每一行的最小值、每一列的最大值全部算出来存进两个数组。rowMin[i]表示第 i 行所有元素里的最小值colMax[j]表示第 j 列所有元素里的最大值这两个数组各扫一遍矩阵就能填满总共 O(n×m)。填完之后再遍历一次矩阵判断a[i][j] rowMin[i] a[i][j] colMax[j]成立就是鞍点。这里用的是相等判定而不是大于等于或小于等于。原因前面提过rowMin[i]本身就是第 i 行的最小值所以a[i][j] 等于它和a[i][j] 是第 i 行的最小值完全等价。相等判定会自动覆盖重复情况不存在漏解。总复杂度降到 O(n×m)额外空间 O(n m)。这就是一个标准的空间换时间代价小得几乎可以忽略。3.2 代码实现#include bits/stdc.h using namespace std; const int MAXN 1005; int a[MAXN][MAXN]; int rowMin[MAXN], colMax[MAXN]; int main() { int n, m; while (cin n m) { for (int i 0; i n; i) for (int j 0; j m; j) cin a[i][j]; // 统计每行的最小值 for (int i 0; i n; i) { rowMin[i] a[i][0]; for (int j 1; j m; j) if (a[i][j] rowMin[i]) rowMin[i] a[i][j]; } // 统计每列的最大值 for (int j 0; j m; j) { colMax[j] a[0][j]; for (int i 1; i n; i) if (a[i][j] colMax[j]) colMax[j] a[i][j]; } bool found false; for (int i 0; i n; i) { for (int j 0; j m; j) { if (a[i][j] rowMin[i] a[i][j] colMax[j]) { cout saddle: ( i , j ) a[i][j] \n; found true; } } } if (!found) cout no saddle point\n; } return 0; }3.3 初始值必须从矩阵里取不能用 0这段代码里唯一真正危险的地方是初始值的选取。rowMin[i] a[i][0]和colMax[j] a[0][j]这两行绝对不能改成 0。原因是求最小值的时候0 并不是一个足够大的中性值它只是一个普通数字。如果整个矩阵全是正整数rowMin[i]被初始化成 0 之后后面的if (a[i][j] rowMin[i])永远不成立最后每一行算出来的最小值都是 0而矩阵里根本没有 0结果就是判定全员失败输出 no saddle point。反过来如果矩阵全是负数colMax[j] 0又会因为 0 比所有元素都大导致每一列的最大值都算成 0同样错得离谱。这类 bug 特别隐蔽因为它在正数用例和负数用例里表现不一样你可能只测了正数矩阵一看输出是 no saddle point以为这组数据本来就没鞍点然后就放过去了。我的做法是固定用INT_MIN/INT_MAX这种极限值做初始化或者像上面代码那样直接取矩阵里的第一个元素两种都行但绝对不用 0。3.4 什么时候方法二就是最优解只要题目给出的规模到了 500×500 以上方法二基本就是标准答案。它代码量不大、逻辑清晰、常数很小实测跑 1000×1000 的随机矩阵通常在十几毫秒以内。而且它的结构非常适合改成只找第一个鞍点就返回的形式遇到就return 0进一步减少无谓遍历。唯一需要留意的是数组开在全局时MAXN要根据题目的实际上限来定开小了会越界有些评测机不会报错只是莫名 WA开太大又浪费内存。稳妥的做法是看一眼题目数据范围往上取个整再留 10% 余量。4. 方法三行指针 候选点验证把重复元素彻底管住4.1 为什么这里要引入行指针方法二用两个数组就解决了问题那方法三的意义在哪在于两件事一是不想开 O(n m) 的额外数组二是想把指针这个 C 里绕不开的话题练熟。二维数组传参一直是初学者的痛点。写成void f(int a[][100])能过写成void f(int **a)就编译不过原因就在于二维数组在内存里是连续的一整块行与行之间是挨着的。要正确描述它你需要的是一个指向一维数组的指针也就是行指针int (*p)[MAXN] a; // p 指向一整行每行 MAXN 个 int写成p[i][j]编译器实际展开成*(*(p i) j)先跳过 i 整行再在当前行内偏移 j 个元素。理解了这一层二维数组和指针之间的关系就通了以后看到vectorvectorint和裸数组的效率差异也不会再觉得神秘。4.2 候选点验证先把一行里所有最小值找全方法三的核心流程是这样逐行处理先扫描当前行求出最小值然后收集该行中所有等于这个最小值的列下标放进一个候选列表。接着对列表里的每一个候选位置去它所在的列上扫一遍看有没有比它更大的元素。没有它就是鞍点。这个流程最大的好处是它不会像记录第一个最小值位置那样漏解。一行里有两个 1两个都会被收进候选列表然后各自去验证列条件该是鞍点的跑不掉不是的也不会被冤枉。代价是候选验证阶段最坏情况下要多花 O(k × n)k 是候选点数量。但实际数据里 k 通常远小于 m而且如果题目保证每行最小值唯一k 恒等于 n总复杂度就退化成 O(n×m)跟方法二持平。4.3 用行指针实现的完整版本#include bits/stdc.h using namespace std; const int MAXN 1005; int a[MAXN][MAXN]; int check(const int (*p)[MAXN], int n, int m) { vectorint cand; int cnt 0; for (int i 0; i n; i) { // 第一步求第 i 行的最小值 int mn *(*(p i) 0); for (int j 1; j m; j) if (*(*(p i) j) mn) mn *(*(p i) j); // 第二步收集所有等于最小值的列下标 cand.clear(); for (int j 0; j m; j) if (*(*(p i) j) mn) cand.push_back(j); // 第三步逐个验证候选点是不是所在列的最大值 for (int idx 0; idx (int)cand.size(); idx) { int j cand[idx]; bool isColMax true; for (int k 0; k n; k) { if (*(*(p k) j) mn) { isColMax false; break; } } if (isColMax) { cout saddle: ( i , j ) mn \n; cnt; } } } return cnt; } int main() { int n, m; while (cin n m) { for (int i 0; i n; i) for (int j 0; j m; j) cin a[i][j]; if (check(a, n, m) 0) cout no saddle point\n; } return 0; }这里check的参数写成const int (*p)[MAXN]加const是为了告诉编译器和阅读代码的人这个函数只读不写不会偷偷改你的矩阵。在实际项目里这个习惯很值钱因为它能在编译期拦下一部分误操作。4.4 用a[i][j]还是*(*(pi)j)上面代码故意用了指针解引用形式是为了把行指针的机制摊开给你看。但说句实话日常写题的时候我几乎都用p[i][j]可读性高得多编译器生成的汇编也完全一样不存在下标写法更慢这种事。真正需要用指针的场合主要两类一是函数传参时想把二维数组传进去二是做底层内存操作比如把整行当作一块连续内存去memcpy或者做 SIMD 优化。除此之外下标写法就是最佳选择别为了用指针而用指针。5. 三种方法的横向对照与常见变形题5.1 一张表看清取舍对比项方法一三重循环方法二预存行最小列最大方法三候选点验证时间复杂度O(n·m·(nm))O(n·m)O(n·m k·n)额外空间O(1)O(nm)O(m)重复元素处理天然正确天然正确天然正确代码量少中中偏多适合规模n,m ≤ 100n,m ≤ 5000依赖候选点数量主要用途对拍基准正式提交练指针、省空间5.2 行最大配列最小的版本怎么改把方法二的代码改成另一种口径只需要改三处求rowMin改成求rowMax求colMax改成求colMin最后比较的大于小于号相应翻转。逻辑框架完全不动。但有个细节很容易被忽略rowMax[i]的初始值要取a[i][0]并且用更新colMin[j]的初始值取a[0][j]并且用更新。这两处的符号方向必须匹配否则算出来的数组要么全错要么刚好在某个特殊用例上蒙对非常难查。5.3 浮点数矩阵和近似鞍点如果矩阵里存的是浮点数判等就不能直接写了必须引入误差容忍const double EPS 1e-9; bool eq(double x, double y) { return fabs(x - y) EPS; }然后把a[i][j] rowMin[i]换成eq(a[i][j], rowMin[i])。这个改动看起来简单但实际影响很大当一行里有两个值相差不到 1e-9 的元素时它们会被同时视为最小值从而凭空多出候选点。所以 EPS 的取值要和题目数据精度匹配盲目取 1e-9 有时候反而会引入误判。还有一种题型是近似鞍点要求找出使 |行最小值 - 列最大值| 最小的位置。这种题就不是判定问题了而是优化问题方法二的思路依然能用算完两个数组后遍历一次矩阵用abs(a[i][j] - rowMin[i])之类的指标打分取最优。数据规模允许的话暴力法也能对付。5.4 稀疏矩阵场景下的取舍如果题目明确说矩阵里 99% 是零还开 1000×1000 的数组就是纯浪费。这时候应该只存非零元素用一组(row, col, val)三元组表示配合哈希表快速查某一行、某一列的数据。这种情况下方法二完全失效反倒是最原始的思路——针对每个非零元素验证它所在行和列——更合适只是需要用哈希表把扫描整行整列替换成查表把复杂度从 O(nm) 降到接近 O(1)。6. 调试清单这些坑我一个个踩过6.1 初始化值取 0 的那次事故前面提过这是我最想强调的一条。当时那道题给的矩阵全是正整数我用rowMin[i] 0初始化跑了一晚上都对不上答案最后拿一组全负数的手工数据一测才恍然大悟——也有人说自己初始化成INT_MAX就万无一失其实求最小值时用INT_MAX是对的但求最大值时用INT_MAX又错了。最稳的做法永远是取矩阵里真实存在的元素做初值或者严格记住求最小用INT_MAX求最大用INT_MIN。6.2 行列下标写反错得不留痕迹a[i][j]里的 i 是行、j 是列这个大家都知道但在嵌套循环里for (int i 0; i n; i)和for (int j 0; j m; j)的嵌套顺序一旦反过来程序照样能跑只是访问内存的顺序变成了跳着走在缓存友好的角度上是灾难而且如果 n 和 m 恰好相等逻辑错误甚至不会暴露。我的防御手段是给变量起有含义的名字比如for (int r 0; r rows; r)和for (int c 0; c cols; c)看到a[r][c]就知道行在前列在后比 i、j 可靠得多。6.3 多组数据时数组没有清理干净如果你把rowMin、colMax这类数组开在while循环外面复用为了省那点初始化时间一定要保证它们在每一组数据里都被完整覆盖。方法二里这两个数组是逐元素赋值的天然不存在残留问题但如果你写的是if (a[i][j] rowMin[i])这种只更新更小的写法就必须在每组开头把它们重置否则上一组的小值会污染下一组。6.4 本地搭建和调试的一点习惯写题时用g -stdc17 -Wall -O2 -o saddle saddle.cpp编译-Wall打开后像变量未使用有符号无符号比较这类问题会直接以警告形式暴露出来能省掉不少排查时间。如果用的是图形化编辑器记得把 C 标准调到 C17并确认头文件路径配置正确否则像bits/stdc.h这种非标准头文件在某些环境下会找不到。调试的时候我更倾向于在关键位置打印数组的中间状态而不是急着上断点。比如算完rowMin之后先把它整行打印出来一眼就能看出是不是全 0 这种明显异常。这种打印中间结果的土办法在算法题里通常比单步调试高效得多尤其是当错误出在数组填充阶段的时候。6.5 关于输出第一个还是输出全部这是最容易被忽略的格式问题。有些题目说输出任意一个鞍点即可那你在找到第一个之后直接return 0是完全可以的还省时间但如果题目说输出所有鞍点或者在没找到时要输出一个特定字符串比如none、no、-1那就必须严格按题面来。我见过不止一次因为多输出了一行空格、或者大小写不一致导致的格式错误。最后分享一个小技巧写完方法二之后把它跟方法一放在同一个 shell 脚本里用几十组随机生成的小矩阵跑对拍。命令层面其实很简单生成数据、跑两个程序、diff一下输出不一致就立刻停下来看数据。这个习惯一旦养成你在处理任何多重条件判定的题目时都会踏实很多因为你知道自己手上永远有一个不会骗人的参照物。