🔥个人主页：Milestone-里程碑

❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>

       <<Git>><<MySQL>>

🌟心向往之行必能至

题目描述

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

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

示例 1：

plaintext

输入：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

---

思路分析：从右上角开始的 “二分” 思维

看到 “有序” 和 “查找”，我们很自然地会想到二分查找。但这道题的矩阵是行有序、列有序，但整体并非完全有序，所以不能直接对整个矩阵进行二分。

这里有一个非常巧妙的思路：从矩阵的右上角开始查找。

1. 初始位置：我们将指针 (i, j) 初始化为 (0, n-1)，也就是第一行最后一列的元素。这个元素是它所在行的最大值，同时也是它所在列的最小值。
2. 比较与移动：
   • 如果 matrix[i][j] == target：恭喜，找到了目标值，直接返回 true。
   • 如果 matrix[i][j] < target：说明当前行的所有元素都小于 target，我们可以直接排除这一行，将指针向下移动一行（i++）。
   • 如果 matrix[i][j] > target：说明当前列的所有元素都大于 target，我们可以直接排除这一列，将指针向左移动一列（j--）。
3. 终止条件：当指针 i 超出矩阵的行数（i >= m）或者 j 小于 0（j < 0）时，说明遍历完了所有可能的路径，目标值不存在，返回 false。

这种方法的时间复杂度是 O(m + n)，空间复杂度是 O(1)，在最坏情况下，我们需要遍历从右上角到左下角的一条路径。

---

C++ 代码实现

cpp

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 获取列数
        int m = matrix[0].size();
        // 获取行数
        int n = matrix.size();
        
        // 初始化指针在右上角 (第一行，最后一列)
        int i = 0;
        int j = m - 1;
        
        // 当指针在矩阵范围内时循环
        while (i < n && j >= 0) {
            if (matrix[i][j] == target) {
                // 找到目标值
                return true;
            } else if (matrix[i][j] < target) {
                // 当前值太小，排除当前行，向下移动
                ++i;
            } else {
                // 当前值太大，排除当前列，向左移动
                --j;
            }
        }
        // 遍历完所有可能，未找到
        return false;
    }
};

---

代码解读

• 初始化：我们首先获取矩阵的行数 n 和列数 m，并将指针 i 和 j 分别定位到矩阵的右上角。
• 核心循环：while (i < n && j >= 0) 确保我们的指针始终在矩阵的有效范围内。
• 决策逻辑：根据当前指针位置的值与目标值的大小关系，我们做出 “向下” 或 “向左” 的移动决策，每一步都能排除一行或一列，从而高效地缩小搜索范围。

---

总结

这道题的关键在于利用矩阵的特殊结构，跳出 “逐行二分” 的思维定式，找到一个能同时利用行和列有序性的切入点。从右上角开始的查找策略，将一个看似复杂的问题，转化成了一个线性时间复杂度的优雅解法。