54.Maximum Spiral Matrix

题目

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

大意

将一个矩阵以螺旋式的方式输出出来。

答案

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if(matrix.size()==0)
        {
            return res;
        }
        int hang = matrix.size();
        int lie =matrix[0].size();
        int hangbegin=0,hangend=hang-1,liebegin=0,lieend=lie-1;
      	//设置四个指针，分别指向行的开始，行的结束，列的开始，列的结束。
      	//大的循环条件就是行开始小于等于行结束，列开始要小于等于列结束。
      	//然后以上，右，下，左的顺序依次输出每个元素。输出完以后修改指针的位置。
        while(hangbegin<=hangend && liebegin<=lieend)
        {
            for(int i=liebegin;i<=lieend;i++)
            {
                res.push_back(matrix[hangbegin][i]);
            }
            hangbegin++;
          	//输出完上面后，行的开始要加1.
            for(int i=hangbegin;i<=hangend;i++)
            {
                res.push_back(matrix[i][lieend]);
            }
            lieend--;
          	//输出完右边后，列的结束要减1.
            if (hangbegin <= hangend) 
            {
                 for(int i=lieend;i>=liebegin;i--)
                {
                    res.push_back(matrix[hangend][i]);
                }
            }//这个if条件和下面的if条件不能去掉，因为在大的while循环里面，hangbegin已经加1了，这样在					//循环中，是有可能hangbegin>hangend的，所以要再加上条件进行判断。下面的if同理。
            hangend--;
          	//输出完下面后行的结束要减1.
            if(liebegin<=lieend)
            {
                for(int i=hangend;i>=hangbegin;i--)
                {
                    res.push_back(matrix[i][liebegin]);
                }
            }
            liebegin++;
          //输出完左边后，列的开始要加1.
        }
        return res;
    }
};

思路

This is a very simple and easy to understand solution. I traverse right and increment rowBegin, then traverse down and decrement colEnd, then I traverse left and decrement rowEnd, and finally I traverse up and increment colBegin.

The only tricky part is that when I traverse down or left I have to check whether the row or col still exists to prevent duplicates.

tips

声明一个n个大小的vector<vector >
vector<vector > res( n, vector(n) );