🔗 搜索二维矩阵 II

题目来源：240. 搜索二维矩阵 II – 力扣（LeetCode）

---

📌 题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

你需要返回 true 如果能在矩阵中找到目标值，否则返回 false。

---

✅ 示例解析

示例 1：

• 输入：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
• 解释：数字 5 存在于矩阵中。

示例 2：

• 输入：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 = 20
• 输出：false
• 解释：数字 20 不存在于矩阵中。

---

⚠️ 提示

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• -10⁹ <= matrix[i][j] <= 10⁹
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -10⁹ <= target <= 10⁹

---

💡 解法：Z 字形查找 —— O(m + n) 时间，O(1) 额外空间

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length - 1; 
        int i = 0, j = n;

        while (i < m && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++; 
            } else {
                j--; 
            }
        }

        return false;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(m + n)
  • 最多进行 m + n 步操作（每次移动一行或一列）。
  • 实际上，每一步都会缩小搜索范围，因此平均情况下的性能可能更好。
• 空间复杂度：O(1) ✅
  • 仅使用常数个额外变量：m, n, i, j。
  • 所有操作均在原矩阵上进行，完全原地计算。

---

🧩 解题思路

1. 核心思想：利用排序特性，Z 字形查找
   • 由于矩阵的每行和每列都是升序排列，可以从右上角开始查找。
   • 若当前元素等于目标值，则找到了；
   • 若当前元素小于目标值，则向下移动（因为下方的元素更大）；
   • 若当前元素大于目标值，则向左移动（因为左侧的元素更小）。
2. 为什么选择右上角？
   • 右上角是一个特殊的起点：
     • 向下可以找到更大的元素（同一列下方的元素更大）。
     • 向左可以找到更小的元素（同一行左边的元素更小）。
   • 相比之下，左上角只能保证右边和下边更大，无法直接决定下一步的方向。
   • 类似地，也可以选择左下角作为起点，逻辑相反。
3. 查找过程：
   • 初始化：i = 0（第 0 行），j = n（最右侧列）。
   • 循环条件：i < m 且 j >= 0（未越界）。
   • 在每个位置 (i, j)：
     1. 若 matrix[i][j] == target，返回 true。
     2. 若 matrix[i][j] < target，则目标值只能在当前行的下方，i++。
     3. 若 matrix[i][j] > target，则目标值只能在当前列的左侧，j--。
   • 循环结束仍未找到，返回 false。
4. 举例说明：
   对 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：
   • 初始：(i=0, j=4) → matrix[0][4] = 15 > 5 → j-- → j=3
   • 下一步：(i=0, j=3) → matrix[0][3] = 11 > 5 → j-- → j=2
   • 再下一步：(i=0, j=2) → matrix[0][2] = 7 > 5 → j-- → j=1
   • 再下一步：(i=0, j=1) → matrix[0][1] = 4 < 5 → i++ → i=1
   • 再下一步：(i=1, j=1) → matrix[1][1] = 5 == target → 返回 true ✅
5. 边界处理：
   • 空矩阵或空行：直接返回 false。
   • 单行/单列：退化为一维有序数组查找问题。
   • 目标值超出矩阵范围：最终会跳出循环，返回 false。