XingHuiSamaの宝藏之地

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

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

示例 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

示例 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

提示：

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

1. 算法核心思想：降维与二叉搜索树抽象

难点在于矩阵元素的递增方向存在两个维度（向右递增、向下递增）。如果选择左上角作为起点，向右和向下均会导致数值变大，在遇到目标值不匹配时，算法将面临方向选择的歧义，极易退化为 O(M×N) 的全局遍历。

本解法的破局点在于起点的巧妙选择。将搜索起点设为右上角（或左下角）后，矩阵的局部拓扑结构实质上被抽象成了一棵二叉搜索树（BST）：

当前节点：右上角元素。
左子树：当前节点左侧的元素（严格小于当前节点）。
右子树：当前节点下方的元素（严格大于当前节点）。

通过这种抽象，原本在二维平面上的盲目搜索，被成功降维成了一条单向的确定性路径。

2. 逻辑拆解

初始化搜索边界：设置指针 r = 0 和 c = cols - 1，将探测点锚定在第一行的最右侧。进入 while 循环，限制条件为 c >= 0 && r < rows，确保指针在向左或向下移动时不会跌出矩阵边界。
执行三岔分支判定：
- 命中目标：若 matrix[r][c] == target，搜索成功，直接返回 true。
- 目标值偏大：若 target > matrix[r][c]，说明当前节点及所在行的所有左侧元素均过小。此时果断舍弃当前整行，执行 r++，让指针向下移动以寻找更大的数值。
- 目标值偏小：若 target < matrix[r][c]，说明当前节点及所在列的所有下方元素均过大。此时果断舍弃当前整列，执行 c--，让指针向左移动以寻找更小的数值。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {

        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<int> now = {0,cols - 1};
        while (now[1] >= 0 && now[0] < matrix.size()) {
            if (matrix[now[0]][now[1]] == target) {
                return true;
            }
            else if (target > matrix[now[0]][now[1]]) {
                now[0]++;
            }
            else {
                now[1]--;
            }
        }
        return false;
    }
};

3. 复杂度剖析

时间复杂度：O(M+N)。其中 M 为矩阵行数，N 为矩阵列数。指针每次移动必定排除一整行或一整列，在最坏情况下，指针从右上角行进至左下角，最多向下移动 M 次，向左移动 N 次，整体耗时呈严格的线性级别。
空间复杂度：O(1)。算法全程基于原二维矩阵进行指针游走，仅开辟了常数级别的整型变量用于记录当前坐标，未占用任何额外的辅助空间。