LeetCode Search a 2D Matrix II - 二維矩陣搜索 II

題目大意

給定一個 m×n 矩陣，每行從左遞增，每列從上遞增。判斷目標值 target 是否存在。例：

[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。

O(m+n) 搜索策略：右上角出發

從 matrix[0][n-1]（右上角）開始：

• 若當前值 > target：說明該列所有值都 > target（列遞增），向左移 col--。
• 若當前值 < target：說明該行所有值都 < target（行遞增），向下移 row++。
• 若相等 → 返回 true。
• 越界 → 返回 false。

每步排除一行或一列，最多 m+n 步。

代碼實現 (Java / C++ / Python)

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) return false;
        int row = 0, col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {
            int val = matrix[row][col];
            if (val > target) col--;
            else if (val < target) row++;
            else return true;
        }
        return false;
    }
}

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 r = 0, c = n - 1;
        while (r < m && c >= 0) {
            if (matrix[r][c] > target) --c;
            else if (matrix[r][c] < target) ++r;
            else return true;
        }
        return false;
    }
};

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]: return False
        r, c = 0, len(matrix[0]) - 1
        while r < len(matrix) and c >= 0:
            val = matrix[r][c]
            if val > target: c -= 1
            elif val < target: r += 1
            else: return True
        return False

為什麼不能從左上角或右下角開始？

• 左上角：值最小，>target 時無法決定向右還是向下（兩方向都可能更大）。
• 右下角：值最大， 時同理無法決策。
• 右上角（或左下角）是「鞍點」：一大一小，決策唯一。