力扣最热一百题——螺旋矩阵
目录
题目链接：54. 螺旋矩阵 - 力扣（LeetCode）
题目描述
示例
提示：
解法一：模拟
1. 边界初始化
2. 循环遍历矩阵
3. 从左到右遍历上边界
4. 从上到下遍历右边界
5. 从右到左遍历下边界
6. 从下到上遍历左边界
7. 结束条件
代码执行流程总结
Java写法：
运行时间以及内存消耗
C++写法：
运行时间以及内存消耗
总结
题目链接：54. 螺旋矩阵 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
解法一：模拟
按照顺时针方向从外圈到内圈依次读取矩阵中的元素。具体实现思路可以分为以下几个步骤：
1. 边界初始化
- 定义四个边界：
top,bottom,left,right，分别表示矩阵的上边界、下边界、左边界和右边界。 - 初始时，
top为 0（最上方），bottom为矩阵的最后一行索引，left为 0（最左边），right为矩阵的最后一列索引。
2. 循环遍历矩阵
- 进入
while循环，条件是：top <= bottom && left <= right。这意味着当矩阵还未完全遍历时，继续循环。 - 在每次循环中，按照四个方向依次遍历：从左到右、从上到下、从右到左、从下到上。每次遍历完一条边界后，收缩该边界（即移动内圈的边界）。
3. 从左到右遍历上边界
- 首先，遍历当前
top行，从left到right，将该行的所有元素依次添加到结果数组中。 - 遍历完成后，将
top变量加 1，表示上边界下移一行，进入内层。
4. 从上到下遍历右边界
- 然后，遍历当前
right列，从top到bottom，将该列的所有元素依次添加到结果数组中。 - 遍历完成后，将
right变量减 1，表示右边界左移一列。
5. 从右到左遍历下边界
- 如果
top <= bottom仍然成立（即还有未遍历的行），开始遍历bottom行，从right到left，将该行的所有元素依次添加到结果数组中。 - 遍历完成后，将
bottom变量减 1，表示下边界上移一行。
6. 从下到上遍历左边界
- 如果
left <= right仍然成立（即还有未遍历的列），开始遍历left列，从bottom到top，将该列的所有元素依次添加到结果数组中。 - 遍历完成后，将
left变量加 1，表示左边界右移一列。
7. 结束条件
- 循环不断缩小边界，直到
top > bottom或left > right，表示已经遍历完所有的元素，此时退出循环。 - 返回保存螺旋顺序的
res数组。
代码执行流程总结
- 每次从四个方向依次遍历矩阵的当前边界。
- 每遍历完一条边界，收缩该边界，进入下一层的螺旋圈。
- 重复上述步骤，直到所有元素都被遍历完。
Java写法：
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix == null || matrix.length == 0) {
return res;
}
int top = 0; // 上边界
int bottom = matrix.length - 1; // 下边界
int left = 0; // 左边界
int right = matrix[0].length - 1; // 右边界
while (top <= bottom && left <= right) {
// 从左到右遍历当前的上边界
for (int i = left; i <= right; i++) {
res.add(matrix[top][i]);
}
top++; // 上边界收缩
// 从上到下遍历当前的右边界
for (int i = top; i <= bottom; i++) {
res.add(matrix[i][right]);
}
right--; // 右边界收缩
// 判断是否还需要遍历
if (top <= bottom) {
// 从右到左遍历当前的下边界
for (int i = right; i >= left; i--) {
res.add(matrix[bottom][i]);
}
bottom--; // 下边界收缩
}
// 判断是否还需要遍历
if (left <= right) {
// 从下到上遍历当前的左边界
for (int i = bottom; i >= top; i--) {
res.add(matrix[i][left]);
}
left++; // 左边界收缩
}
}
return res;
}
}
运行时间以及内存消耗
C++写法：
#include <vector>
using namespace std;
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
if (matrix.empty() || matrix[0].empty()) {
return res;
}
int top = 0; // 上边界
int bottom = matrix.size() - 1; // 下边界
int left = 0; // 左边界
int right = matrix[0].size() - 1; // 右边界
while (top <= bottom && left <= right) {
// 从左到右遍历当前的上边界
for (int i = left; i <= right; i++) {
res.push_back(matrix[top][i]);
}
top++; // 上边界收缩
// 从上到下遍历当前的右边界
for (int i = top; i <= bottom; i++) {
res.push_back(matrix[i][right]);
}
right--; // 右边界收缩
// 判断是否还需要遍历
if (top <= bottom) {
// 从右到左遍历当前的下边界
for (int i = right; i >= left; i--) {
res.push_back(matrix[bottom][i]);
}
bottom--; // 下边界收缩
}
// 判断是否还需要遍历
if (left <= right) {
// 从下到上遍历当前的左边界
for (int i = bottom; i >= top; i--) {
res.push_back(matrix[i][left]);
}
left++; // 左边界收缩
}
}
return res;
}
};
运行时间以及内存消耗
总结
这里的边界条件实在是非常的难把握，所实话，一但掉入了边界条件的陷阱之后就会让你一直缝缝补补，很难有几率能缝缝补补出来。
正如那句话所说：一如入循环深似海，从此offer是路人
