LeetCode矩阵算法精解：高频题目与优化技巧

1. 矩阵算法实战LeetCode高频题目精解矩阵类算法题是面试中的常客尤其在大厂技术面中几乎必考。这类题目看似简单但要在有限时间内写出最优解需要掌握特定的技巧和思维模式。今天我们就来深度剖析LeetCode中四道经典的矩阵题目从暴力解法到最优方案一步步拆解其中的算法思维。2. 矩阵置零LeetCode 732.1 问题分析与常规解法给定一个m×n的矩阵如果一个元素为0则将其所在行和列的所有元素都设为0。要求原地修改矩阵即不使用额外空间。最直观的解法是使用两个标记数组分别记录需要置零的行和列。具体步骤第一次遍历矩阵记录有0的行和列第二次遍历矩阵根据记录将对应行列置零这种方法的时间复杂度是O(mn)空间复杂度是O(mn)因为需要额外的数组存储标记。2.2 优化思路与原地算法面试官通常期待更优的空间复杂度解法。我们可以利用矩阵本身的第一行和第一列来存储标记class Solution { public void setZeroes(int[][] matrix) { boolean firstRowHasZero false; boolean firstColHasZero false; // 检查第一行是否有零 for (int j 0; j matrix[0].length; j) { if (matrix[0][j] 0) { firstRowHasZero true; break; } } // 检查第一列是否有零 for (int i 0; i matrix.length; i) { if (matrix[i][0] 0) { firstColHasZero true; break; } } // 使用第一行和第一列记录零位置 for (int i 1; i matrix.length; i) { for (int j 1; j matrix[0].length; j) { if (matrix[i][j] 0) { matrix[i][0] 0; matrix[0][j] 0; } } } // 根据标记置零 for (int i 1; i matrix.length; i) { if (matrix[i][0] 0) { for (int j 1; j matrix[0].length; j) { matrix[i][j] 0; } } } for (int j 1; j matrix[0].length; j) { if (matrix[0][j] 0) { for (int i 1; i matrix.length; i) { matrix[i][j] 0; } } } // 处理第一行和第一列 if (firstRowHasZero) { for (int j 0; j matrix[0].length; j) { matrix[0][j] 0; } } if (firstColHasZero) { for (int i 0; i matrix.length; i) { matrix[i][0] 0; } } } }关键点使用两个额外变量记录第一行和第一列是否原本就有零避免标记被覆盖导致错误。3. 螺旋矩阵LeetCode 543.1 问题描述与边界处理给定一个m行n列的矩阵按照顺时针螺旋顺序返回所有元素。例如输入matrix [[1,2,3],[4,5,6],[7,8,9]] 输出[1,2,3,6,9,8,7,4,5]这道题的难点在于边界条件的处理特别是当矩阵不是正方形时。3.2 分层模拟法最直观的方法是分层处理从外向内一层层遍历class Solution { public ListInteger spiralOrder(int[][] matrix) { ListInteger result new ArrayList(); if (matrix null || matrix.length 0) return result; int top 0, bottom matrix.length - 1; int left 0, right matrix[0].length - 1; while (true) { // 从左到右遍历上层 for (int j left; j right; j) result.add(matrix[top][j]); if (top bottom) break; // 从上到下遍历右层 for (int i top; i bottom; i) result.add(matrix[i][right]); if (--right left) break; // 从右到左遍历下层 for (int j right; j left; j--) result.add(matrix[bottom][j]); if (--bottom top) break; // 从下到上遍历左层 for (int i bottom; i top; i--) result.add(matrix[i][left]); if (left right) break; } return result; } }注意事项每次完成一个方向的遍历后都要检查边界是否相遇避免重复遍历。4. 旋转图像LeetCode 484.1 数学规律分析给定一个n×n的二维矩阵表示一个图像要求将图像顺时针旋转90度。必须在原地旋转图像即直接修改输入的二维矩阵。旋转图像的关键是找到位置映射关系。经过分析可以发现顺时针旋转90度等价于先转置矩阵然后反转每一行逆时针旋转90度等价于先反转每一行然后转置矩阵4.2 原地旋转实现class Solution { public void rotate(int[][] matrix) { int n matrix.length; // 转置矩阵 for (int i 0; i n; i) { for (int j i; j n; j) { int temp matrix[i][j]; matrix[i][j] matrix[j][i]; matrix[j][i] temp; } } // 反转每一行 for (int i 0; i n; i) { int left 0, right n - 1; while (left right) { int temp matrix[i][left]; matrix[i][left] matrix[i][right]; matrix[i][right] temp; left; right--; } } } }技巧转置时j从i开始避免重复交换。反转行时使用双指针法更高效。5. 搜索二维矩阵IILeetCode 2405.1 问题特点与暴力解法编写一个高效的算法来搜索m×n矩阵matrix中的一个目标值target。该矩阵具有以下特性每行的元素从左到右升序排列每列的元素从上到下升序排列暴力解法是遍历整个矩阵时间复杂度O(mn)显然不是最优解。5.2 利用矩阵特性的搜索策略由于矩阵的特殊排序性质可以从右上角开始搜索如果当前元素等于target返回true如果当前元素大于target向左移动一列排除当前列如果当前元素小于target向下移动一行排除当前行class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix null || matrix.length 0) return false; int row 0, col matrix[0].length - 1; while (row matrix.length col 0) { if (matrix[row][col] target) { return true; } else if (matrix[row][col] target) { col--; } else { row; } } return false; } }时间复杂度分析最坏情况下从右上角走到左下角时间复杂度O(mn)6. 矩阵算法总结与技巧6.1 常见解题模式标记法利用矩阵本身存储额外信息如矩阵置零问题边界收缩法通过调整边界逐步缩小搜索范围如螺旋矩阵、搜索矩阵数学变换法利用数学规律实现高效操作如图像旋转双指针法从两个方向同时搜索如搜索矩阵II6.2 面试注意事项先确认矩阵是否为正方形行和列的处理可能不同注意边界条件特别是空矩阵和单行/单列矩阵优先考虑能否利用矩阵本身存储额外信息以减少空间复杂度画图辅助理解元素位置变化关系在实际面试中建议先阐述暴力解法然后逐步优化。清晰地表达你的思考过程比直接给出最优解更重要。对于矩阵问题多在白板上画出矩阵变化过程有助于发现规律和避免错误。