解题思路

马鞍数是指在一行中最小、同时在这一列中最大的数。要求找出所有这样的数并输出位置，没有就输出 not exist。

思路：

1. 逐行处理：先找出这一行的最小值 mini
2. 对每个等于 mini 的格子，找出它所在列的最大值 maxj
3. 如果 mini 等于 maxj，说明这个数既是行最小又是列最大，就是马鞍数
4. 输出它的行号、列号和值
5. 如果从头到尾一个都没找到，输出 not exist

为什么要逐个检查等于 mini 的格子？ 因为一行里可能有多个格子都等于最小值，每个都要判断是不是马鞍数。

举例：

5 6 7 8 9
4 5 6 7 8
3 4 5 2 1
2 3 4 9 0
1 2 5 4 8

• 第 1 行最小值是 5（第 1 列），第 1 列最大值也是 5，所以 (1,1) 是马鞍数

参考代码

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int a[15][15] = {};
    bool found = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }

    for (int i = 1; i <= n; i++) {
        int mini = a[i][1];  // 找行最小值
        for (int j = 2; j <= m; j++) {
            if (a[i][j] < mini) mini = a[i][j];
        }

        for (int j = 1; j <= m; j++) {
            if (mini == a[i][j]) {
                int maxj = a[1][j];  // 找列最大值
                for (int k = 2; k <= n; k++) {
                    if (a[k][j] > maxj) maxj = a[k][j];
                }
                if (mini == maxj) {  // 行最小且列最大
                    found = 1;
                    cout << i << " " << j << " " << mini << endl;
                }
            }
        }
    }

    if (found == 0) cout << "not exist";
    return 0;
}

复杂度分析

• 时间复杂度：O(N²×M)，逐行找最小值再逐格找列最大值
• 空间复杂度：O(N×M)，二维数组存矩阵