力扣hot100-240.搜索二维矩阵2-单调性剪枝详解

LeetCode 240. 搜索二维矩阵 II单调性剪枝详解1. 算法思想这题属于矩阵搜索 / 单调性剪枝也常被称为 Z 字形搜索。它不是普通二分查找每一行、每一列分别有序但整个矩阵按行展开后并不整体有序。例如[ [1, 4, 7], [2, 5, 8], [3, 6, 9] ]按行展开是1, 4, 7, 2, 5, 8, 3, 6, 9其中7后面是2因此不能把它当一维数组二分。本题的关键是从右上角开始每次比较都能确定排除一整行或一整列。2. 为什么从右上角开始右上角matrix[0][n - 1]有两个相反的单调方向左边都更小。 下面都更大。因此当前位置matrix[row][col]与target比较后移动方向是确定的current target向左排除当前列。 current target向下排除当前行。 current target找到答案。当前值过大为什么排除当前列如果current target当前列从上到下递增。从当前行往下的元素都满足matrix[i][col] current target整列都太大不可能有答案因此col--;当前值过小为什么排除当前行如果current target当前行从左到右递增。当前剩余区域中这一行从左边界到当前列的所有元素都满足matrix[row][j] current target整行都太小不可能有答案因此row;3. 用 target 5 完整模拟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] ]从右上角开始row 0, col 4当前值 15 15 5向左。 row 0, col 3当前值 11 11 5向左。 row 0, col 2当前值 7 7 5向左。 row 0, col 1当前值 4 4 5向下。 row 1, col 1当前值 5 找到目标。路径是15 - 11 - 7 - 4 | v 5因此这类搜索也叫 Z 字形搜索。4. 为什么不会漏掉答案当前位置始终是当前剩余区域的右上角。当前值大于 target当前列下面的值更大整列排除安全。 当前值小于 target当前行左边的值更小整行排除安全。每一步删除的都是确定不可能包含target的区域。搜索会在找到目标或剩余区域为空时结束因此不会漏掉答案。5. Java 代码完整注释classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){// 空矩阵中不存在目标。if(matrix.length0||matrix[0].length0){returnfalse;}intmmatrix.length;intnmatrix[0].length;// 从右上角开始。introw0;intcoln-1;// row 只向下移动col 只向左移动。// 任一指针越界时说明剩余区域为空。while(rowmcol0){intcurrentmatrix[row][col];if(currenttarget){returntrue;}if(currenttarget){// 当前列从上到下递增下面的元素只会更大。// 所以当前列不可能有 target向左排除它。col--;}else{// 当前行从左到右递增左边的元素只会更小。// 所以当前行不可能有 target向下排除它。row;}}returnfalse;}}6. 左下角也可以左下角同样有相反的单调方向上面更小右边更大。因此从左下角开始也可以当前值大于 target向上。 当前值小于 target向右。它与右上角写法本质相同。学习时固定记住右上角版本即可大了向左小了向下。7. 复杂度分析每一步只会向左移动一列或者向下移动一行。最多向左 n 次。 最多向下 m 次。所以时间复杂度是O(m n)额外空间复杂度是O(1)8. 总结这题属于矩阵搜索 / 单调性剪枝。从右上角开始当前值 target当前列全都太大向左。 当前值 target当前行全都太小向下。每一步排除一整行或一整列因此效率是O(m n)。一句话记忆从右上角开始大了向左小了向下。