企业官网建设流程全解析

LeetCode-Book：LCR 121「寻找目标值 - 二维数组」二叉搜索树视角的线性搜索解法详解

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

导读

本文围绕《LeetCode-Book》仓库中 LCR 121. 寻找目标值 - 二维数组 一题展开，讲解如何利用矩阵「从上到下递增、从左到右递增」的单调性，把搜索过程等价为在一棵隐式二叉搜索树上的查找，从而将暴力遍历的 $O(NM)$ 复杂度降为 $O(M+N)$。读完本文，你将掌握「从角落出发的消行消列搜索法」这一经典二维数组查找套路，并能在 Python、Java、C++ 三种语言中独立写出可运行的解法；同时，通过仓库中同源题目的多语言实现与测试用例，理解该算法在《剑指 Offer 04》与 LeetCode 240 号题之间的对应关系。

题目背景与仓库中的位置

「LCR 121. 寻找目标值 - 二维数组」是《剑指 Offer》中“二维数组中的查找”的力扣 LCR 版本，题干把矩阵抽象为一座“仓库”的plants（植物库存）矩阵，要求判断target是否存在于其中。该题在仓库中与以下内容同源：

• 解法文档：leetbook_ioa/docs/LCR 121. 寻找目标值 - 二维数组.md
• 《剑指 Offer》同名题文档：sword_for_offer/docs/剑指 Offer 04. 二维数组中的查找.md
• LeetCode 240「搜索二维矩阵 II」文档：selected_coding_interview/docs/240. 搜索二维矩阵 II.md

三份材料对应的解法代码分别存放在仓库的sword_for_offer/codes与selected_coding_interview/codes目录中，算法思想完全一致，读者可对照阅读。

暴力法为何不是最优解

若直接双重循环遍历整个plants矩阵，时间复杂度为 $O(NM)$（$N$ 为行数、$M$ 为列数）。该做法完全没有利用矩阵的单调递增特性：

• 每一行从左到右递增；
• 每一列从上到下递增。

暴力法的缺点在于：每次只比较一个元素，无法根据比较结果排除整行或整列，因此最坏情况下要把矩阵中每个元素都访问一遍。显然，在面试与竞赛场景下这不是最优解法，正确思路是利用矩阵的结构性质做“排除法”。

核心思路：将矩阵视作一棵二叉搜索树

文档给出了一个非常直观的模型：将矩阵逆时针旋转 45°并转化为图的形式，可以发现矩阵的单调结构与二叉搜索树（BST）完全同构——对于每个元素，其“左分支”方向上的元素更小，“右分支”方向上的元素更大。

利用这一性质，可以选取矩阵中「左下角」或「右上角」的元素作为整棵树的“根节点”开始搜索：

• 遇到比target大的元素，就向“左”走（消去当前行）；
• 遇到比target小的元素，就向“右”走（消去当前列）。

之所以选择左下角或右上角作为起点，是因为这两个位置的元素具备“一条方向递增、另一条方向递减”的特殊性：从左下角出发，向上（行号减小）元素递减，向右（列号增大）元素递增，恰好对应 BST 中“左小右大”的分支关系，从而保证每轮比较都能确定性地消去一行或一列。

算法流程

以plants的左下角元素为起始点，索引记为(i, j)：

1. 从(i, j)开始遍历，与target对比：
   • 当plants[i][j] > target时，执行i--，即消去第i行；
   • 当plants[i][j] < target时，执行j++，即消去第j列；
   • 当plants[i][j] == target时，返回true，代表找到目标值。
2. 若行索引i < 0或列索引j >= M发生越界，则说明矩阵中不存在目标值，返回false。

关键不变量：每轮i或j移动后，相当于生成了一个“消去一行（列）后的新矩阵”，索引(i, j)恰好指向新矩阵的左下角元素。因此可以反复套用上述性质持续消行消列，直到命中目标或指针越界。

该搜索过程的终止条件只有两种：要么命中target，要么指针越界走出矩阵边界——绝不会出现“死循环”或漏查，因为每轮迭代都会严格消除一行或一列，最多进行 $M+N$ 次比较。

多语言代码实现

Python

class Solution: def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool: i, j = len(plants) - 1, 0 while i >= 0 and j < len(plants[0]): if plants[i][j] > target: i -= 1 elif plants[i][j] < target: j += 1 else: return True return False

Java

class Solution { public boolean findTargetIn2DPlants(int[][] plants, int target) { int i = plants.length - 1, j = 0; while (i >= 0 && j < plants[0].length) { if (plants[i][j] > target) i--; else if (plants[i][j] < target) j++; else return true; } return false; } }

C++

class Solution { public: bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) { int i = plants.size() - 1, j = 0; while (i >= 0 && j < plants[0].size()) { if (plants[i][j] > target) i--; else if (plants[i][j] < target) j++; else return true; } return false; } };

三种语言的实现完全同构：i从最后一行出发（len(plants) - 1/plants.length - 1/plants.size() - 1），j从第 0 列出发；循环条件i >= 0 && j < 列数同时充当“未越界”与“未命中”的守卫；循环体内按大小关系三分支处理，命中即返回true，循环自然结束返回false。

复杂度分析

• 时间复杂度 $O(M+N)$：其中 $N$ 为矩阵行数、$M$ 为矩阵列数。每轮迭代必然使i减 1 或j加 1，i最多从 $N-1$ 递减到 0，j最多从 0 递增到 $M-1$，因此循环次数上界为 $M+N$，与暴力法的 $O(NM)$ 相比有显著提升。
• 空间复杂度 $O(1)$：仅使用i、j两个指针变量，占用常数大小的额外空间。

仓库源码印证：同源三题的可运行测试用例

本解法并非孤立存在，仓库在同一目录树中收录了该算法的多个可运行版本，代码中带完整的测试驱动（Driver Code），可直接编译运行验证：

• 剑指 Offer 04（Python）：sword_for_offer/codes/python/sfo_04_find_a_number_in_2d_matrix_s1.py 使用测试矩阵与target = 5，运行后打印True；
• 剑指 Offer 04（Java）：sword_for_offer/codes/java/sfo_04_find_a_number_in_2d_matrix_s1/sfo_04_find_a_number_in_2d_matrix_s1.java；
• 剑指 Offer 04（C++）：sword_for_offer/codes/cpp/sfo_04_find_a_number_in_2d_matrix_s1/sfo_04_find_a_number_in_2d_matrix_s1.cpp；
• LeetCode 240（Java）：selected_coding_interview/codes/java/lc_240_search_a_2d_matrix/lc_240_search_a_2d_matrix.java；
• LeetCode 240（C++）：selected_coding_interview/codes/cpp/lc_240_search_a_2d_matrix_ii/lc_240_search_a_2d_matrix_ii_s1.cpp。

各版本统一使用如下 5×5 单调矩阵作为测试用例：

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

以 C++ 版本 sfo_04_find_a_number_in_2d_matrix_s1.cpp 为例，其main函数构造矩阵并调用findNumberIn2DArray(matrix, 5)，期望输出true。读者可以替换target的值（例如改为20）验证返回false的路径，从而完整覆盖“命中提前返回”与“指针越界返回 false”两条分支。从源码结构可以推断，仓库作者（Krahets）刻意保持了三个题库目录（leetbook_ioa、sword_for_offer、selected_coding_interview）中该题实现的一致性，便于读者跨题对照学习同一核心算法。

变体与易错点

1. 起点也可选右上角：与左下角对称，从右上角(0, M-1)出发，向右（j++）元素递增、向下（i++）元素递减，同样可行；循环条件相应变为i < N && j >= 0。两种写法等价，面试时可任选一种并说明理由。
2. 必须选“拐角”而非任意点：只有左下角或右上角同时具备两个方向的单调性，才能保证每轮确定性地排除一整行或一整列；若从左上角出发，两个方向都递增，无法判断应该消行还是消列。
3. 越界条件的顺序：循环条件必须同时检查i >= 0与j < M，两者缺一不可，否则访问plants[i][j]时可能产生数组越界异常。
4. 空矩阵处理：若plants为空行或列为 0，初始化i = -1或j >= 0不成立，循环直接不执行并返回false，天然安全，无需额外判空。

总结

LCR 121 的核心价值在于提供了一个“化矩阵为树”的思维范式：面对有序的二维结构，优先寻找具备双向单调性的角落作为搜索起点，利用一次比较排除整行或整列，最终把二维查找化简为一条从角落到目标的最短路径。掌握这一套路后，无论是 剑指 Offer 04. 二维数组中的查找 还是 240. 搜索二维矩阵 II，都可以在数分钟内写出同样的最优解——这正是该题被三大题库同时收录的原因所在。

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book