搜索二维矩阵 II

怎样从“每行递增、每列递增的 m x n 矩阵里判断 target 是否存在。”推导出 矩阵 / 有序性 / Z 字形搜索 / 右上角分水岭，并证明每次状态变化都不会漏掉答案？

中心结论：从右上角出发:大了左移删列,小了下移删行。

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

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

在本站主例中，每行递增、每列递增的 m x n 矩阵里判断 target 是否存在。

算法最终需要得到或观察：target=5 返回 true,target=20 返回 false。

凭感觉逐格转向容易重复或漏掉边角；固定方向和边界收缩保证每个格子恰好处理一次。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“矩阵边界框”，明确答案需要观察什么。
2. 2状态只维护 row/col 指针。
3. 3转移每一步按照 从右上角出发:大了左移删列,小了下移删行。
4. 4收尾读取 target=5 返回 true,target=20 返回 false。，并复核边界与复杂度。

每走完一条边，只收紧刚刚完成的那一侧边界。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：row/col 指针。

给出一个二维矩阵，矩阵的特点是每一个行内，元素随着下标增大而增大，每一列内，元素也是随着下标增大而增大。但是相邻两行的元素并没有大小关系。例如第一行最后一个元素就比第二行第一个元素要大。要求设计一个算法能在这个矩阵中高效的找到一个数，如果找到就输出 true，找不到就输出 false。 这一题是第 74 题的加强版。第 74 题中的二维矩阵完全是一个有序的一维矩阵，但是这一题如果把它拍扁成一维，并不是有序的。首先每一个行或者每一列是有序的 ，那么我们可以依次在每一行或者每一列中利用二分去搜索。这样做时间复杂度为 O(n log n)。 还有一个模拟的解法。通过观察，我们发现了这个矩阵的一个特点，最右边一列的元素是本行中最大的元素，所以我们可以先从最右边一列开始找到第一个比 target 元素大的元素，这个元素所在的行，是我们接着要搜索的。在行中搜索是从最右边开始往左边搜索，时间复杂度是 O(n)，算上一开始在最右边一列中查找的时间复杂度是 O(m)，所以最终的时间复杂度为 O(m+n)。

从右上角出发:大了左移删列,小了下移删行。

执行过程中持续维护：row/col 指针。

正确性依赖以下不变量：右上左下走法每步排除一行或列。

面试时可以压缩为：从右上角开始,每次排除一行或一列,时间 O(m+n),空间 O(1)。

落到当前题，执行机制可以压缩为：从右上角出发:大了左移删列,小了下移删行。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入每行递增、每列递增的 m x n 矩阵里判断 target 是否存在。 因为：从右上角出发:大了左移删列,小了下移删行。
2. 2从右上角开始 Z 形搜索利用行列有序性。 因为：每次排除一行或一列。
3. 311 > 5,左移移动指针。 因为：单调排除搜索空间。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 57 > 5,左移移动指针。 因为：单调排除搜索空间。
6. 64 < 5,下移移动指针。 因为：单调排除搜索空间。
7. 7找到目标返回 true。 因为：O(m+n)。
8. 8收尾与复杂度target=5 返回 true,target=20 返回 false。 因为：时间 O(m+n) · 空间 O(1)。从右上角出发:大了左移删列,小了下移删行。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一 模拟，时间复杂度 O(m+n)
func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 {
		return false
	}
	row, col := 0, len(matrix[0])-1
	for col >= 0 && row <= len(matrix)-1 {
		if target == matrix[row][col] {
			return true
		} else if target > matrix[row][col] {
			row++
		} else {
			col--
		}
	}
	return false
}

// 解法二 二分搜索，时间复杂度 O(n log n)
func searchMatrix2401(matrix [][]int, target int) bool {
	if len(matrix) == 0 {
		return false
	}
	for _, row := range matrix {
		low, high := 0, len(matrix[0])-1
		for low <= high {
			mid := low + (high-low)>>1
			if row[mid] > target {
				high = mid - 1
			} else if row[mid] < target {
				low = mid + 1
			} else {
				return true
			}
		}
	}
	return false
}

func main() {
    // 1. 主例
    //    输入：mode="search-2d", 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
    //    期望：target=5 返回 true,target=20 返回 false。
    //
    // 2. 失败 / 未命中
    //    检查：左上/右下不行会漏。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC74 二维矩阵；LC378 第 K 小
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意每行递增、每列递增的 m x n 矩阵里判断 target 是否存在。
2. 2重复凭感觉逐格转向容易重复或漏掉边角；固定方向和边界收缩保证每个格子恰好处理一次。
3. 3优化从右上角出发:大了左移删列,小了下移删行。
4. 4证明右上左下走法每步排除一行或列。
5. 5复杂度时间 O(m+n)，空间 O(1)