LeetCode 解题思路 10（Hot 100）

解题思路：

1. 上边： 从左到右遍历顶行，完成后上边界下移（top++）。
2. 右边： 从上到下遍历右列，完成后右边界左移（right–）。
3. 下边： 从右到左遍历底行，完成后下边界上移（bottom–）。
4. 左边： 从下到上遍历左列，完成后左边界右移（left++）。

Java代码：

class Solution {public List<Integer> spiralOrder(int[][] matrix) {if (matrix.length == 0) return null;List<Integer> res = new ArrayList<>();int left = 0, top = 0;int bottom = matrix.length - 1;int right = matrix[0].length - 1;while (left <= right && top <= bottom) {for (int i = left; i <= right; i++)res.add(matrix[top][i]);top++;if (left > right || top > bottom) break;for (int i = top; i <= bottom; i++)res.add(matrix[i][right]);right--;if (left > right || top > bottom) break;for (int i = right; i >= left; i--)res.add(matrix[bottom][i]);bottom--;if (left > right || top > bottom) break;for (int i = bottom; i >= top; i--)res.add(matrix[i][left]);left++;if (left > right || top > bottom) break;}return res;}
}

复杂度分析：

• 时间复杂度： O(mn)，其中 m 为矩阵的行数，n 为列数。每个元素最多被访问一次。
• 空间复杂度： O(1)，仅使用常数级别的额外空间维护边界变量，输出结果所需的空间不计入额外复杂度。

解题思路：

1. 矩阵分圈处理： 将矩阵视为由多个同心层组成（如最外层、次外层等）。
2. 四次交换完成单圈旋转： 对于每一层的每个分组（由 i 和 j 确定），通过 ​四次元素交换​ 实现顺时针旋转：
   temp = matrix[i][j] → 保存当前元素
   matrix[i][j] = matrix[n-j-1][i] → 左上角元素被替换为左下角元素
   matrix[n-j-1][i] = matrix[n-i-1][n-j-1] → 左下角元素被替换为右下角元素
   matrix[n-i-1][n-j-1] = matrix[j][n-i-1] → 右下角元素被替换为右上角元素
   matrix[j][n-i-1] = temp → 右上角元素被替换为临时保存的原始左上角元素

Java代码：

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;for (int i = 0; i < n / 2; ++i) {for (int j = 0; j < (n + 1) / 2; ++j) {int temp = matrix[i][j];matrix[i][j] = matrix[n - j - 1][i];matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];matrix[j][n - i - 1] = temp;}}}
}

复杂度分析：

• 时间复杂度： O(n²)，每个元素被访问一次，且每次访问仅进行常数次操作。其中 n 是矩阵的边长。
• 空间复杂度： O(1)，仅使用固定数量的变量（如 temp），没有额外开辟存储空间。