Spiral Matrix II

• 问题介绍
  • 问题描述：Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
  • 示例：
    • Input: 3
    • Output: [
      [ 1, 2, 3 ],
      [ 8, 9, 4 ],
      [ 7, 6, 5 ]
      ]
  • 约束条件：NULL
• 解决思路
  • 思路：除了螺旋型的输入，还有波浪型等等，这类问题都可以用O(n)的时间复杂度解决，其中n表示矩阵的元素个数；具体解决思路为：
    • 为了让我们访问矩阵的时候按照题目要求的顺序，我们需要设置一个能够表示方向的变量，在该题中，设置up_or_down，l_or_r两个变量，分别表示此时访问矩阵的方式是向上还是向下，向左还是向右，在一个方向上的遍历到边界后，需要更新方向的值使其对应下一个方向；
    • 还需要注意的一个问题就是，每个方向的遍历后，会影响其他方向遍历的边界，例如首先处于矩阵[0,0]位置进行向右的遍历后，第一行矩阵都赋值了，在后面向上的遍历时，就不能访问到第一行的元素了，因为他们已经被赋值了，所以在当前方向遍历后需要将其影响的方向上的边界值进行更新；本题中设置了l_limit,r_limit,up_limit,down_limit分别表示四个方向能够访问到的位置的约束，其对应的更新规则分别如下：当在向右遍历一行后，up_limit相应的需要+1；当在向左遍历一行后，down_limit需要-1；当在向上遍历一列后，l_limit相应需要+1；在向下遍历一列后，r_limit相应需要-1；
    • 同时在访问完矩阵的一个方向后，需要将访问的位置更新到对应的下一个方向的起点，对于一个4X4的矩阵，访问的模拟过程如下图：
    • 
    • 这样只需要访问矩阵一次，时间复杂度为O(n)，就可以实现按螺旋顺序给矩阵赋值，如果是对于从已经赋值好的矩阵中按螺旋的顺序读出数据，同样可以采用这种思路；
• 代码

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> resp(n,vector<int>(n,0));
        int m=n;
        int l_or_r=1;//左右方向
        int up_or_down=0;//上下方向
        
        int l_limit=0;
        int r_limit=n;
        int up_limit=0;
        int down_limit=m;
        
        int col=0;
        int row=0;        
        int count=n*n; 
        for(int i=1;i<=n*n;)
        {
            if(l_or_r==1)//向右
            {
                while(col<r_limit)
                {
                    resp[row][col]=i;
                    col++;
                    i++;
                }
                col--;
                row++;
                l_or_r=0;
                up_or_down=1;
                up_limit+=1;
            }
            if(l_or_r==-1)//向左
            {
                while(col>=l_limit)
                {
                    resp[row][col]=i;
                    col--;
                    i++;
                }
                col++;
                row--;
                l_or_r=0;
                up_or_down=-1; 
                down_limit-=1;
            }
            if(up_or_down==1)//向下
            {
                while(row<down_limit)
                {
                    resp[row][col]=i;
                    row++;
                    i++;
                }
                row--;
                col--;
                l_or_r=-1;
                up_or_down=0; 
                r_limit-=1;
            } 
            if(up_or_down==-1)//向上
            {
                while(row>=up_limit)
                {
                    resp[row][col]=i;
                    i++;
                    row--;
                }
                row++;
                col++;
                l_or_r=1;
                up_or_down=0; 
                l_limit+=1;
            }             
        }
        return resp;
    }
};