螺旋矩阵

题面

给你一个 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.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

分析

• 对于这种问题，可以定义一个方向数组，当达到边界条件时，就更改方向，直到最终达到最后的位置

• 需要注意的是，随着一整论循环的增加，其边界条件的判定也应该修改

• 模拟即可

  class Solution {
  public:
      vector<int> spiralOrder(vector<vector<int>>& matrix) {
          vector<int> dx = {0, 1, 0, -1};
          vector<int> dy = {1, 0, -1, 0};
          vector<int> result;
          int x = 0, y = 0, cur = matrix.size() * matrix[0].size();
          int direction = 0;
          int loop = 0;
          bool added_loop = false;
          while (cur-- > 0) {
              result.push_back(matrix[x][y]);
              if (!added_loop && direction == 3) {
                  loop++;
                  added_loop = true;
              }
              // std::cout << loop << " " << x << " " << y << " " << std::endl;
              if ((direction == 0 && y == matrix[0].size() - 1 - loop) ||
                  (direction == 1 && x == matrix.size() - 1 - loop) ||
                  (direction == 2 && y == loop) ||
                  (direction == 3 && x == loop)) {
                  direction = (direction + 1) % 4;
                  added_loop = false;
              }
              x += dx[direction];
              y += dy[direction];
              // std::cout << x << " " << y << " " << std::endl;
          }
          return result;
      }
  };

• 可以用边界收缩法代替原代码复杂的方向 + loop 判定逻辑

  #include <vector>
  using namespace std;
  
  class Solution {
  public:
      vector<int> spiralOrder(vector<vector<int>>& matrix) {
          // 处理空矩阵的特殊情况
          if (matrix.empty() || matrix[0].empty()) {
              return {};
          }
          
          vector<int> result;
          // 定义四个边界
          int top = 0;                  // 上边界
          int bottom = matrix.size() - 1; // 下边界
          int left = 0;                 // 左边界
          int right = matrix[0].size() - 1; // 右边界
          
          // 当边界不交叉时继续遍历
          while (top <= bottom && left <= right) {
              // 1. 从左到右遍历上边界
              for (int i = left; i <= right; ++i) {
                  result.push_back(matrix[top][i]);
              }
              top++; // 上边界向下收缩
              
              // 2. 从上到下遍历右边界
              for (int i = top; i <= bottom; ++i) {
                  result.push_back(matrix[i][right]);
              }
              right--; // 右边界向左收缩
              
              // 防止单行/单列时重复遍历
              if (top > bottom || left > right) {
                  break;
              }
              
              // 3. 从右到左遍历下边界
              for (int i = right; i >= left; --i) {
                  result.push_back(matrix[bottom][i]);
              }
              bottom--; // 下边界向上收缩
              
              // 4. 从下到上遍历左边界
              for (int i = bottom; i >= top; --i) {
                  result.push_back(matrix[i][left]);
              }
              left++; // 左边界向右收缩
          }
          
          return result;
      }
  };