题目描述

顺时针打印矩阵

样例

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

(暴力枚举) $O(n^2)$

控制上下左右四个角，每次列举好从一个顶点到另一个顶点。枚举完后更新角的位置。

时间复杂度 O(n * m)

C++ 代码

#define x first
#define y second
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if (matrix.empty() || matrix[0].empty()) return res;
        int n = matrix.size(), m = matrix[0].size();
        typedef pair<int, int> PII;
        //left top | right top | left down | right down
        PII lt = {0, 0}, rt = {0, m - 1}, ld = {n - 1, 0}, rd = {n - 1, m - 1};
        bool add = false;
        while (1)
        {
            add = false;
            for (int i = lt.y; i <= rt.y - 1 && lt.x >= 0 && lt.x <= n - 1; i ++) res.push_back(matrix[lt.x][i]), add = true;
            for (int i = rt.x; i <= rd.x - 1 && rt.y >= 0 && rt.y <= m - 1; i ++) res.push_back(matrix[i][rt.y]), add = true;
            for (int i = rd.y; i >= ld.y + 1 && rd.x >= 0 && rd.x <= n - 1; i --) res.push_back(matrix[rd.x][i]), add = true;
            for (int i = ld.x; i >= lt.x + 1 && ld.y >= 0 && ld.y <= m - 1; i --) res.push_back(matrix[i][ld.y]), add = true;
            if (res.size() == n * m || !add) break;
            lt.x ++, lt.y ++;
            rt.x ++, rt.y --;
            ld.x --, ld.y ++;
            rd.x --, rd.y --;
        }
        if (res.size() < n * m) res.push_back(matrix[lt.x][lt.y]);
        else {
            int delta = res.size() - n * m;
            while (delta > 0)
            {
                res.pop_back();
                delta --;
            }
        }
        return res;
    }
};