解析

//! wrong answer
class Solution {
public:
  vector<int> spiralOrder(vector<vector<int>> &matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    vector<int> res(m * n);

    int i = 0, j = 0, index = 0, dir = 0;
    int leftBound = 0, rightBound = n - 1, upBound = 0, downBound = m - 1;
    vector<vector<int>> direction = {
        {0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上
    while (leftBound < rightBound && upBound < downBound) {
      res[index++] = matrix[i][j];
      if (dir == 0 && j == rightBound) { // 右碰壁
        ++upBound;
        dir = (dir + 1) % 4;
      } else if (dir == 1 && i == downBound) {
        --rightBound;
        dir = (dir + 1) % 4;
      } else if (dir == 2 && j == leftBound) {
        --downBound;
        dir = (dir + 1) % 4;
      } else if (dir == 3 && i == upBound) {
        ++leftBound;
        dir = (dir + 1) % 4;
      }

      i += direction[dir][0];
      j += direction[dir][1];
    }
    ++dir;

    return res;
  }
};

//! n*m,1 -> 一次遍历，常数空间
class Solution {
public:
  vector<int> spiralOrder(vector<vector<int>> &matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    int leftBound = 0, rightBound = n - 1, upBound = 0, downBound = m - 1;
    int index = 0;
    vector<int> res(m * n);
    while (leftBound <= rightBound || upBound <= downBound) {
      // 从左到右
      for (int j = leftBound; j <= rightBound; ++j) {
        res[index++] = matrix[upBound][j];
      }
      ++upBound;
      if (upBound > downBound) {
        break;
      }

      // 从上到下
      for (int i = upBound; i <= downBound; ++i) {
        res[index++] = matrix[i][rightBound];
      }
      --rightBound;
      if (leftBound > rightBound) {
        break;
      }

      // 从右到左
      for (int j = rightBound; j >= leftBound; --j) {
        res[index++] = matrix[downBound][j];
      }
      --downBound;
      if (upBound > downBound) {
        break;
      }

      // 从下到上
      for (int i = downBound; i >= upBound; --i) {
        res[index++] = matrix[i][leftBound];
      }
      ++leftBound;
      if (leftBound > rightBound) {
        break;
      }
    }
    return res;
  }
};