LeetCode 240 搜索二維矩陣 II：右上角搜索法 O(m+n)

題目描述

給定一個 m x n 矩陣，滿足：

• 每行從左到右遞增
• 每列從上到下遞增

判斷目標值是否存在。注意：與 Matrix I 不同，此處行首不保證大於上行尾。

範例：

matrix = [
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
target = 5 → true
target = 20 → false

解題思路：右上角（或左下角）消除法

從右上角 (0, n-1) 開始：

• 當前值 == target → 找到
• 當前值 > target → 當前列所有值都 > target，左移 排除該列（col--）
• 當前值 < target → 當前行所有值都 < target，下移 排除該行（row++）

每步排除一行或一列，最多 m + n 步。時間複雜度：O(m + n)，空間複雜度：O(1)。

C++ 參考實現

class Solution {
public:
    bool searchMatrix(vector>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        
        int m = matrix.size(), n = matrix[0].size();
        int row = 0, col = n - 1;  // 右上角起始
        
        while (row < m && col >= 0) {
            int val = matrix[row][col];
            if (val == target) return true;
            else if (val > target) col--;  // 排除當前列
            else row++;                     // 排除當前行
        }
        return false;
    }
};

Python 參考實現

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:
            return False
        
        m, n = len(matrix), len(matrix[0])
        row, col = 0, n - 1
        
        while row < m and col >= 0:
            val = matrix[row][col]
            if val == target:
                return True
            elif val > target:
                col -= 1
            else:
                row += 1
        return False

核心要點總結

• 起點選擇：右上角或左下角（有「一大一小」決策性質），左上/右下無法決策
• 消除邏輯：利用行列單調性，每步確定排除整行或整列
• 對比 Matrix I：Matrix I 全局有序可二分 O(log mn)；Matrix II 只有局部有序，需 O(m+n) 線性搜索
• 圖示輔助：建議畫 3x3 小矩陣演練決策過程

這是二維矩陣搜索的經典「階梯搜索」模式，掌握後可解決類似「行列遞增矩陣查找/統計/路徑」問題。