LeetCode 240 Search a 2D Matrix II：右上角搜索法

題目描述

在 m x n 矩陣中搜索目標值。矩陣特性：每行從左遞增，每列從上遞增。判斷目標值是否存在。

最優解法：右上角（或左下角）搜索

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

• 若 matrix[i][j] == target，返回 true。
• 若 matrix[i][j] > target，說明當前列所有元素均大於目標（列遞增），左移 j--。
• 若 matrix[i][j] < target，說明當前行所有元素均小於目標（行遞增），下移 i++。
• 越界則返回 false。

時間空間複雜度

• 時間：O(m + n)，每步排除一行或一列。
• 空間：O(1)。

Java 參考代碼

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

面試高頻考點

• 利用矩陣「行增列增」的偏序性質，將二維搜索轉化為一維決策。
• 同樣適用於左下角起始。
• 若矩陣改為「行增列減」等，需調整起始點與移動方向。