一、矩阵置零
1、题目
73. 矩阵置零 - 力扣（LeetCode）
2、分析
如果我们遍历到 0，就马上在原矩阵上修改行、列为 0（红色），那么后面待遍历的元素就被修改了，会导致误修改很多行、列（绿色）：
法一，使用额外的矩阵：遍历原矩阵，在这个新矩阵上进行修改。
时间复杂度 O(mn)，空间复杂度 O(mn)。
法二，使用额外的两个数组：先标记每行、每列是否置零，再根据标记置零。
时间复杂度 O(mn)，空间复杂度 O(m+n)。
法三，使用额外的一个变量（最优）：直接用原矩阵的第一行和第一列标记每行、列是否需要置零（1 不置零，0 置零）。[0,0] 已经被第一行用过，所以1个额外的变量代表第一列的 [0,0] 位置。
如图情况：第一行原本有0（需置零），但第一列原本没有 0（不需置零）。如果第一行、列公用 [0,0]，就会把第一行、列都标记为需要置零。
时间复杂度 O(mn)，空间复杂度 O(1)。
3、代码
class Solution {public void setZeroes(int[][] matrix) {int row = matrix.length, col = matrix[0].length;int colFlag = 1;// 检测第一行、第一列是否要置零for (int i = 0; i < row; i++) {if (matrix[i][0] == 0) {colFlag = 0;break;}}for (int j = 0; j < col; j++) {if (matrix[0][j] == 0) {matrix[0][0] = 0;break;}}// 检测其它行、列for (int i = 1; i < row; i++) {for (int j = 1; j < col; j++) {if (matrix[i][j] == 0) {matrix[0][j] = 0;matrix[i][0] = 0;}}}// 根据第一行、列的标记置零for (int i = 1; i < row; i++) {for (int j = 1; j < col; j++) {if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;}}// 置零第一行、第一列if (matrix[0][0] == 0) {for (int j = 0; j < col; j++) matrix[0][j] = 0;}if (colFlag == 0) {for (int i = 0; i < row; i++) matrix[i][0] = 0;}}
}二、螺旋矩阵
1、题目
54. 螺旋矩阵 - 力扣（LeetCode）
2、分析
搞清四个边界：上、下、左、右，为了便于遍历，把右、下边界设置为最后一个 index 的下一个位置。
搞清四个方向：每一轮循环，都要执行 正序遍历列（更新右边界） >> 正序遍历行（更新下边界） >> 倒序遍历列（更新左边界） >> 倒序遍历行（更新上边界）。
循环结束条件：上边界与下边界重合，或者左边界与右边界重合。
3、代码
class Solution {public List spiralOrder(int[][] matrix) {int top = 0, bottom = matrix.length;int left = 0, right = matrix[0].length;List ret = new ArrayList<>();while (left < right && top < bottom) {// 正序遍历列for (int j = left; j < right; j++) ret.add(matrix[top][j]);top++;if (top >= bottom) break;// 正序遍历行for (int i = top; i < bottom; i++) ret.add(matrix[i][right-1]);right--;if (left >= right) break;// 倒序遍历列for (int j = right-1; j >= left; j--) ret.add(matrix[bottom-1][j]);bottom--;if (top >= bottom) break;// 倒序遍历行for (int i = bottom-1; i >= top; i--) ret.add(matrix[i][left]);left++;}return ret;}
} 三、旋转图像
1、题目
48. 旋转图像 - 力扣（LeetCode）
2、分析
如示例1，把 1 旋转到 3 位置，把 3 旋转到 9 位置...，但是这样会把后面的数给覆盖掉（另想办法）。然后相对 1 偏移 1 个位置的 2 也旋转到 相对 3 偏移一个位置的 6...。旋转完一层后，L、R、T、B 都向里缩一层，直到 L 与 R 重合。
方法一：复制原矩阵，创建额外的矩阵（防止被覆盖）。从复制矩阵取数，在原矩阵上旋转。
时间复杂度：O(n^2)，空间复杂度：O(n^2)。
方法二：先把 1 存储下来，再倒着旋转：7 到 1 位置，9 到 7 位置，3 到 9 位置，最后额外变量中的 1 放到 3 位置。
时间复杂度：O(n^2)，空间复杂度：O(1)。
3、代码
class Solution {public void rotate(int[][] matrix) {int n = matrix.length;int left = 0, right = n-1;int top = 0, bottom = n-1;int tmp = 0;// 遍历每一层（外到内）while (left < right) {// 遍历偏移量for (int i = 0; i < right-left; i++) {tmp = matrix[top][left+i];matrix[top][left+i] = matrix[bottom-i][left];matrix[bottom-i][left] = matrix[bottom][right-i];matrix[bottom][right-i] = matrix[top+i][right];matrix[top+i][right] = tmp;}// 往内缩一层top++;bottom--;left++;right--;}}
}四、最佳买股票时机（贪心）
1、题目
121. 买卖股票的最佳时机 - 力扣（LeetCode）
2、分析
法一，暴力遍历：枚举 (买入, 卖出)，找最大差。
时间复杂度：O(n^2)。
法二：求 max(卖出价格 - newMin)。
时间复杂度：O(n)，空间复杂度：O(1)。
3、代码
class Solution {public int maxProfit(int[] prices) {int min = Integer.MAX_VALUE;int maxRet = 0;int n = prices.length;for (int i = 1; i < n; i++) {min = Math.min(min, prices[i-1]);maxRet = Math.max(maxRet, prices[i] - min);}return maxRet;}
}