C語言經典算法：鞍點查找（矩陣中行最大且列最小元素）

C語言經典算法：鞍點查找（矩陣中行最大且列最小元素）

「鞍點」源於馬鞍形狀：沿脊線方向最低（行極小），垂直方向最高（列極大）。在矩陣中定義為：**某行最大、某列最小**的元素。本文給出標準查找算法、代碼實現與數學直覺解析。

數學定義

對矩陣 a[m][n]，若存在元素 a[i][j] 滿足：

• a[i][j] = max(row i) （第 i 行最大）
• a[i][j] = min(col j) （第 j 列最小）

則稱 a[i][j] 為鞍點。一個矩陣可能有 0 個、1 個或多個鞍點。

算法思路：兩遍掃描法

1. 先找每行最大值及其列索引
2. 再檢查該元素是否為所在列最小值
3. 若是，輸出鞍點位置與值

C 語言實現（3x3 矩陣演示）

#include 

int main() {
    int a[3][3] = {{16, 2, 3}, {14, 5, 6}, {7, 8, 9}};
    int i, j, k, row_max_col, found = 0;
    int max_val;

    for (i = 0; i < 3; i++) {
        // 1. 找第 i 行最大值及其列
        max_val = a[i][0];
        row_max_col = 0;
        for (j = 1; j < 3; j++) {
            if (a[i][j] > max_val) {
                max_val = a[i][j];
                row_max_col = j;
            }
        }

        // 2. 檢查該元素是否為第 row_max_col 列最小
        int is_min = 1;
        for (k = 0; k < 3; k++) {
            if (a[k][row_max_col] < max_val) {
                is_min = 0;
                break;
            }
        }

        if (is_min) {
            printf("鞍點值: %d, 位置: [%d][%d]\n", max_val, i, row_max_col);
            found = 1;
        }
    }

    if (!found) printf("矩陣中無鞍點\n");
    return 0;
}

運行示例

對矩陣：

16  2  3
14  5  6
 7  8  9

• 第 0 行最大 16 (列 0)，檢查第 0 列：16, 14, 7 → 最小是 7 ≠ 16 ✗
• 第 1 行最大 14 (列 0)，檢查第 0 列：最小 7 ≠ 14 ✗
• 第 2 行最大 9 (列 2)，檢查第 2 列：3, 6, 9 → 最小是 3 ≠ 9 ✗
• **無鞍點**

修改矩陣為 {{1,2,3},{4,5,6},{7,8,9}}，則 7 是第 2 行最大、第 0 列最小 → **鞍點為 7**。

鞍點幾何直覺

• 馬鞍面：騎馬時前後穩（脊線最低）、左右易掉（兩側最高）
• 微分方程：某方向穩定、另一方向不穩定的平衡點
• 博弈論：零和遊戲中的極小極大策略對應鞍點

複雜度與優化

• 時間：O(m * n) 兩遍掃描，已是理論下界（必須讀完所有元素）
• 空間：O(1) 額外空間
• 優化：可預計算每行最大、每列最小存入兩個輔助數組，查找變 O(1)，適合多次查詢場景

鞍點問題是「行列極值交互」的經典縮影，掌握其雙重掃描邏輯，對解決矩陣極值、博弈均衡、圖論割點等問題極有啟發。