【Hot 100 刷题计划】 LeetCode 240. 搜索二维矩阵 II | C++ 巧妙利用单调性 (BST 法)
LeetCode 240. 搜索二维矩阵 II
📌 题目描述
题目级别：中等
编写一个高效的算法来搜索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
💡 破题思路：站在右上角，把矩阵看作二叉搜索树 (BST)
这道题虽然行和列都是单调递增的，但上一行的末尾不一定小于下一行的开头，因此整体不具备绝对的一维单调性，无法直接套用全局二分查找。
破局点在于选择“正确的起跑线”！
如果我们在左上角起跑，往右是变大，往下也是变大，一旦当前值小于目标值，我们根本不知道该往右走还是往下走。
但如果我们站在矩阵的右上角，奇妙的物理性质出现了：
- 向左走：同一行中，左边的元素一定比当前小。
- 向下走：同一列中，下边的元素一定比当前大。
这不就是一棵**二叉搜索树（BST）**吗！当前元素就是根节点，左边的行就是左子树，下边的列就是右子树。
核心运作机制：
- 从右上角
(0, n-1)开始搜寻。 - 如果
当前值 == target，直接找到，返回true。 - 如果
当前值 > target，说明目标值不可能在当前列的下方，我们应该向左移动（剔除当前列），即j--。 - 如果
当前值 < target，说明目标值不可能在当前行的左方，我们应该向下移动（剔除当前行），即i++。 - 当越界时说明矩阵中不存在该目标值，返回
false。
💻 C++ 代码实现 (极简贪心法)
classSolution{public:boolsearchMatrix(vector<vector<int>>&matrix,inttarget){intm=matrix.size();if(m==0)returnfalse;intn=matrix[0].size();// 将起点设置在矩阵的右上角inti=0,j=n-1;// 只要没有越过矩阵的左边界和下边界，就继续搜索while(i<m&&j>=0){if(matrix[i][j]==target){returntrue;// 命中靶心}if(matrix[i][j]>target){j--;// 当前值太大了，往左走寻找更小的值}else{i++;// 当前值太小了，往下走寻找更大的值}}// 走出矩阵也没找到，说明不存在returnfalse;}};