LeetCode 240 搜索二維矩陣 II：從暴力解法到最優 Z 字形查找

LeetCode 240 搜索二維矩陣 II：從暴力解法到最優 Z 字形查找

題目描述

編寫高效算法在 m x n 矩陣中搜索目標值。矩陣特性：

• 每行元素從左遞增
• 每列元素從上遞增

示例矩陣：

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

解法演進

❌ 解法一：暴力遍歷 + List.contains (O(mn) 時間，O(mn) 空間)

public boolean searchMatrix(int[][] matrix, int target) {
    List list = new ArrayList<>();
    for (int[] row : matrix)
        for (int val : row)
            list.add(val);
    return list.contains(target);
}

缺點：額外空間、未利用矩陣有序特性、時間複雜度高。

✅ 解法二：右上角 Z 字形查找 (O(m+n) 時間，O(1) 空間) — 最優解

核心思想：從右上角 (或左下角) 開始，利用行列單調性「排除」區域：

• 當前值 > target → 向左移（排除當前列，因該列所有值均更大）
• 當前值 < target → 向下移（排除當前行，因該行所有值均更小）
• 相等 → 找到

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
    
    int rows = matrix.length, cols = matrix[0].length;
    int r = 0, c = cols - 1; // 從右上角開始
    
    while (r < rows && c >= 0) {
        int cur = matrix[r][c];
        if (cur == target) return true;
        else if (cur > target) c--;  // 太大，往左
        else r++;                    // 太小，往下
    }
    return false;
}

📊 複雜度對比

關鍵洞察

矩陣的「行遞增、列遞增」特性構成了部分有序結構，右上角（或左下角）是唯一能同時決定「往左走更小、往下走更大」的決策點，這是解題的幾何直覺核心。

擴展練習

• LeetCode 74：搜索二維矩陣 I（更嚴格：每行首元素 > 上行尾元素，可展平為一維二分）
• 若矩陣極大（如 10^5 x 10^5），可考慮分治或多線程並行 Z 字形搜索