每日一题——螺旋矩阵

题目

给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。

数据范围：0≤n,m≤10，矩阵中任意元素都满足 ∣val∣≤100

要求：空间复杂度 O(nm) ，时间复杂度 O(nm)

示例1

输入：
[[1,2,3],[4,5,6],[7,8,9]]
返回值：
[1,2,3,6,9,8,7,4,5]

示例2

输入：
[]
返回值：
[]

思路

• 首先排除矩阵为空的情况的特殊情况。
• 设置矩阵的四个边界值，开始准备螺旋遍历矩阵，遍历的截止点是左右边界或者上下边界重合。
• 首先对最上面一排从左到右进行遍历输出，到达最右边后第一排就输出完了，上边界相应就往下一行，要判断上下边界是否相遇相交。
• 然后输出到了右边，正好就对最右边一列从上到下输出，到底后最右边一列已经输出完了，右边界就相应往左一列，要判断左右边界是否相遇相交。
• 然后对最下面一排从右到左进行遍历输出，到达最左边后最下一排就输出完了，下边界相应就往上一行，要判断上下边界是否相遇相交。
• 然后输出到了左边，正好就对最左边一列从下到上输出，到顶后最左边一列已经输出完了，左边界就相应往右一列，要判断左右边界是否相遇相交。
• 重复上述遍历操作直到循环结束。

解答代码

#include <vector>
class Solution {
public:
    /**
     * @param matrix int整型vector<vector<>> 
     * @return int整型vector
     */
    vector<int> spiralOrder(vector<vector<int> >& matrix) {
        // write code here
        auto row_size = matrix.size();
        if (row_size == 0) {
            return vector<int>{};
        }
        auto col_size = matrix[0].size();
        // 上边界
        int top = 0;
        // 下边界
        int bottom = row_size - 1;
        // 左边界
        int left = 0;
        // 右边界
        int right = col_size - 1;
        vector<int> res;
        while (top <= bottom && left <= right) {
            // 从左到右遍历上边界
            for (int i = left; i <= right; i++) {
                res.push_back(matrix[top][i]);
            }
            // 上边界下移
            ++top;
            if (top > bottom)
                break;
            // 从上到下遍历右边界
            for (int i = top; i <= bottom; i++) {
                res.push_back(matrix[i][right]);
            }
            // 左移右边界
            --right;
            if (right < left)
                break;
            // 从右到左遍历下边界
            for (int i = right; i >=left; i--) {
                res.push_back(matrix[bottom][i]);
            }
            // 上移下边界
            --bottom;
            if (bottom < top)
                break;
            // 从下到上遍历左边界
            for (int i = bottom; i >= top; i--) {
                res.push_back(matrix[i][left]);
            }
            // 右移左边界
            ++left;
            if (left > right)
                break;
        }
        return res;
    }
};