C 語言二維陣列實戰：鞍點問題（行最大中的最小、行最小中的最大）

問題定義

給定 n×n 整數矩陣，求：

1. 各行最大值中的最小值
2. 各行最小值中的最大值

演算法流程

1. 輸入矩陣階數與元素。
2. 遍歷每行：
   • 找行最大值 row_max，更新全域 min_of_max。
   • 找行最小值 row_min，更新全域 max_of_min。
3. 輸出兩結果。

關鍵代碼

int min_of_max = 0, max_of_min = 0;
for (int r=0; r row_max) row_max = matrix[r][c];
        if (matrix[r][c] < row_min) row_min = matrix[r][c];
    }
    if (r==0) { min_of_max = row_max; max_of_min = row_min; }
    else {
        if (row_max < min_of_max) min_of_max = row_max;
        if (row_min > max_of_min) max_of_min = row_min;
    }
}
printf("Min of row max: %d\nMax of row min: %d\n", min_of_max, max_of_min);

複雜度與變體

• 時間 O(n²)，空間 O(1) 額外空間。
• 若改為「列最大中的最小」等，只需交換迴圈順序。
• 此即博弈論中的「鞍點」概念，矩陣遊戲最小化最大損失策略。