54. Spiral Matrix

題目網址：https://leetcode.cn/problems/spiral-matrix/

題意：給一 m x n 的 matrix, 按照 順時針螺旋 順序, 返回 matrix 中所有元素。

Solution：

想法： 將 matrix 由外而內分成好幾層, 每層都有四個方向要走, 依序是

• 由左至右
• 由上至下
• 由右至左
• 由下至上

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int left = 0, right = matrix[0].size();
        int top = 0, bottom = matrix.size();
        int direction = 0;

        while (left < right && top < bottom) {
            if (direction == 0) {
                // 得到 top row 的元素
                for (int i = left; i < right; ++i) {
                    res.emplace_back(matrix[top][i]);
                }
                ++top;
            } else if (direction == 1) {
                // 得到 right col 的元素
                for (int i = top; i < bottom; ++i) {
                    res.emplace_back(matrix[i][right - 1]);
                }
                --right;
            } else if (direction == 2) {
                // 得到 bottom row 的元素
                for (int i = right - 1; i >= left; --i) {
                    res.emplace_back(matrix[bottom - 1][i]);
                }
                --bottom;
            } else if (direction == 3) {
                // 得到 left col 的元素
                for (int i = bottom - 1; i >= top; --i) {
                    res.emplace_back(matrix[i][left]);
                }
                ++left;
            }

            direction = (direction + 1) % 4;
        }

        return res;
    }
};

• time：$O(m \cdot n)$ ➔ 遍歷 matrix
• space：$O(1)$ ➔ 只需常數空間