LeetCode 240. 搜索二维矩阵 II：单调性剪枝详解
1. 算法思想
这题属于：
1矩阵搜索 / 单调性剪枝 2
也常被称为 Z 字形搜索。它不是普通二分查找：每一行、每一列分别有序，但整个矩阵按行展开后并不整体有序。
例如：
1[ 2 [1, 4, 7], 3 [2, 5, 8], 4 [3, 6, 9] 5] 6
按行展开是 1, 4, 7, 2, 5, 8, 3, 6, 9，其中 7 后面是 2，因此不能把它当一维数组二分。
本题的关键是：从右上角开始，每次比较都能确定排除一整行或一整列。
2. 为什么从右上角开始
右上角 matrix[0][n - 1] 有两个相反的单调方向：
1左边都更小。 2下面都更大。 3
因此当前位置 matrix[row][col] 与 target 比较后，移动方向是确定的：
1current > target：向左，排除当前列。 2current < target：向下，排除当前行。 3current == target：找到答案。 4
当前值过大，为什么排除当前列
如果：
1current > target 2
当前列从上到下递增。从当前行往下的元素都满足：
1matrix[i][col] >= current > target 2
整列都太大，不可能有答案，因此：
1col--; 2
当前值过小，为什么排除当前行
如果：
1current < target 2
当前行从左到右递增。当前剩余区域中，这一行从左边界到当前列的所有元素都满足：
1matrix[row][j] <= current < target 2
整行都太小，不可能有答案，因此：
1row++; 2
3. 用 target = 5 完整模拟
1matrix = 2[ 3 [1, 4, 7, 11, 15], 4 [2, 5, 8, 12, 19], 5 [3, 6, 9, 16, 22], 6 [10, 13, 14, 17, 24], 7 [18, 21, 23, 26, 30] 8] 9
从右上角开始：
1row = 0, col = 4，当前值 15 215 > 5，向左。 3 4row = 0, col = 3，当前值 11 511 > 5，向左。 6 7row = 0, col = 2，当前值 7 87 > 5，向左。 9 10row = 0, col = 1，当前值 4 114 < 5，向下。 12 13row = 1, col = 1，当前值 5 14找到目标。 15
路径是：
115 -> 11 -> 7 -> 4 2 | 3 v 4 5 5
因此这类搜索也叫 Z 字形搜索。
4. 为什么不会漏掉答案
当前位置始终是当前剩余区域的右上角。
1当前值大于 target：当前列下面的值更大，整列排除安全。 2当前值小于 target：当前行左边的值更小，整行排除安全。 3
每一步删除的都是确定不可能包含 target 的区域。搜索会在找到目标，或剩余区域为空时结束，因此不会漏掉答案。
5. Java 代码完整注释
1class Solution { 2 public boolean searchMatrix(int[][] matrix, int target) { 3 // 空矩阵中不存在目标。 4 if (matrix.length == 0 || matrix[0].length == 0) { 5 return false; 6 } 7 8 int m = matrix.length; 9 int n = matrix[0].length; 10 11 // 从右上角开始。 12 int row = 0; 13 int col = n - 1; 14 15 // row 只向下移动，col 只向左移动。 16 // 任一指针越界时，说明剩余区域为空。 17 while (row < m && col >= 0) { 18 int current = matrix[row][col]; 19 20 if (current == target) { 21 return true; 22 } 23 24 if (current > target) { 25 // 当前列从上到下递增，下面的元素只会更大。 26 // 所以当前列不可能有 target，向左排除它。 27 col--; 28 } else { 29 // 当前行从左到右递增，左边的元素只会更小。 30 // 所以当前行不可能有 target，向下排除它。 31 row++; 32 } 33 } 34 35 return false; 36 } 37} 38
6. 左下角也可以
左下角同样有相反的单调方向：上面更小，右边更大。
因此从左下角开始也可以：
1当前值大于 target：向上。 2当前值小于 target：向右。 3
它与右上角写法本质相同。学习时固定记住右上角版本即可：
1大了向左，小了向下。 2
7. 复杂度分析
每一步只会向左移动一列，或者向下移动一行。
1最多向左 n 次。 2最多向下 m 次。 3
所以时间复杂度是：
1O(m + n) 2
额外空间复杂度是：
1O(1) 2
8. 总结
这题属于矩阵搜索 / 单调性剪枝。
从右上角开始：
1当前值 > target：当前列全都太大，向左。 2当前值 < target：当前行全都太小，向下。 3
每一步排除一整行或一整列，因此效率是 O(m + n)。
一句话记忆：
1从右上角开始：大了向左，小了向下。 2
《力扣hot100-240.搜索二维矩阵2-单调性剪枝详解》 是转载文章，点击查看原文。
