难度: Medium
m*n 的二维数组 plants 记录了园林景观的植物排布情况，具有以下特性：
请判断 plants 中是否存在目标高度值 target。
示例 1：
输入：plants = [[2,3,6,8],[4,5,8,9],[5,9,10,12]], target = 8 输出：true
示例 2：
输入：plants = [[1,3,5],[2,5,7]], target = 4 输出：false
提示：
0 <= n <= 10000 <= m <= 1000注意：本题与主站 240 题相同：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
运行时间: 40 ms
内存: 17.3 MB
from typing import List
class Solution:
"""
站在右上角看
这个矩阵其实就像是一个Binary Search Tree
"""
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
row, col = 0, len(matrix) and len(matrix[0])
while row < len(matrix) and col > 0:
if matrix[row][col-1] == target:
return True
elif matrix[row][col-1] > target:
col -= 1
else:
row += 1
return False
该题解采用从右上角开始搜索的方法来查找目标值。考虑二维数组的每一行从左到右递增，每一列从上到下递增的特性，可以将右上角元素视作一个分水岭：如果目标值小于该元素，则目标不可能出现在当前元素的所在列（因为下方的元素都比当前元素大），因此向左移动；如果目标值大于该元素，则目标不可能出现在当前元素的所在行（因为左侧的元素都比当前元素小），因此向下移动。这样逐步缩小搜索范围，直到找到目标值或者确认目标值不存在。
时间复杂度: O(m+n)
空间复杂度: O(1)
from typing import List
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
# 初始化行和列索引，从右上角开始
row, col = 0, len(matrix) and len(matrix[0])
while row < len(matrix) and col > 0: # 确保索引在矩阵范围内
if matrix[row][col-1] == target: # 检查当前元素是否为目标值
return True
elif matrix[row][col-1] > target: # 如果当前元素大于目标值，向左移动
col -= 1
else: # 如果当前元素小于目标值，向下移动
row += 1
return False # 如果退出循环仍未找到目标值，返回False
从右上角开始搜索的方法是基于矩阵的行和列都是递增的特性。右上角的元素具有独特的属性：它是所在行中最大的同时也是所在列中最小的。这种属性使得每一步决策（向左或向下移动）能有效地排除一行或一列。相比之下，从左上角开始，向右和向下都是递增，无法有效使用目标值与当前元素的比较来排除行或列；从左下角或右下角开始类似，都不如右上角的起始位置有效。
如果目标值等于右上角的元素，搜索过程会立即终止。根据代码逻辑，检查到目标值等于当前元素时，会直接返回True，表示找到了目标值，无需进一步搜索其他部分的矩阵。
在当前元素大于目标值时选择向左移动而不是向上移动，是因为向上移动到上一行仍然会面对同样大或更大的元素，因此不能有效排除任何错误的可能性。而向左移动可以排除当前列中所有较大的元素，因为整列元素都是递增的。这样做有效缩小了搜索范围，增加了查找效率。
该算法确实对空矩阵或部分空行有处理，这体现在初始化列索引时用到的条件表达式 `len(matrix) and len(matrix[0])`。这一表达式确保如果矩阵为空或任何一行为空，则列索引为0，从而使得循环条件不成立，直接返回False。因此，算法能正确处理空矩阵或含空行的情况，不会引发错误。