leetcode498对角线遍历

超、凢脫俗 2022-10-05 01:56 121阅读 0赞

![在这里插入图片描述][20210605191920598.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
思路：  
mat\[i\]\[j\]

1.  i+j为偶数时向上
2.  i+j为奇数时向下

可以由图看出，当向下时

1.  到达下边界向右
2.  到达左边界向下

当向上时

1.  到达右边界向下
2.  到达上边界向右

注意判断的顺序是有要求的

1.  例如矩阵向上到达右上顶点时，同时触发两个边界值但是是向下的，所以右边界向下先判断定值。
2.  当矩阵向下到达左下顶点的时候，同时出发两个边界值条件，但是是向右的，所以下边界向右先判断定值。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]  
    代码

vector<int> findDiagonalOrder(vector<vector<int>>& mat) { 
      int len = mat[0].size()-1,high = mat.size()-1;
      int all =(len+1)*(high+1);
      int i=0,j=0,k=0;
      vector<int> res;
      while(k<all){ 
          res.push_back(mat[j][i]);
          if((i+j)%2==0)//偶数层向上遍历，到达右边界向下，到达上边界向右
          { 
              if(i==len){ //到达右边界，向下
                  j++;
              }
              else if(j==0){ //到达上边界，向右
                  i++;
              }
              else //未到边界
              { 
                  j--;i++;
              }
          }
          else//奇数层向下遍历，到达左边界向下，到达下边界向右
          { 
              if(j==high)//下边界
                  i++;
              else if(i==0)//左边界
                  j++;
              else{ 
                  j++;i--;
              }
          }
          k++;
      }
      return res;
    }

[20210605191920598.png]: /images/20221005/74449802cc73423f90d557c2abbc9dc7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20221005/44706734f2254497b1ad1c942e0db056.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20221005/df5ca2025d8448eda2942d51b5b7c939.png