【Hot 100 刷题计划】 LeetCode 240. 搜索二维矩阵 II | C++ 巧妙利用单调性 (BST 法)

张开发
• 2026/4/16 10:59:04 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【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(vectorvectorintmatrix,inttarget){intmmatrix.size();if(m0)returnfalse;intnmatrix[0].size();// 将起点设置在矩阵的右上角inti0,jn-1;// 只要没有越过矩阵的左边界和下边界就继续搜索while(imj0){if(matrix[i][j]target){returntrue;// 命中靶心}if(matrix[i][j]target){j--;// 当前值太大了往左走寻找更小的值}else{i;// 当前值太小了往下走寻找更大的值}}// 走出矩阵也没找到说明不存在returnfalse;}};

更多文章