class Solution {public:    vector
    
      printZMatrix(vector
     
      
        > &matrix) {        vector
       
         v;        if (matrix.size() == 0) return v;        int m = matrix.size(), n = matrix[0].size(), cnt = m * n;        int i = 0, j = 0;        int d[][2] = {
   { -1, 1 }, { 1, -1 }};        int dir = 0;        while (v.size() < cnt) {            while (i >= 0 && i < m && j >= 0 && j < n) {                v.push_back(matrix[i][j]);                i += d[dir][0];                j += d[dir][1];            }            i -= d[dir][0];            j -= d[dir][1];            if (dir == 0) {                if (j + 1 < n) ++j;                else ++i;            } else {                if (i + 1 < m) ++i;                else ++j;            }            dir = (dir + 1) % 2;        }        return v;    }};
       
      
     
    

思路:

• 斜着走的方向只有"右上"(dir=0)和"左下"(dir=1). 按"右上", "左下"的顺序交替走.
• 当走到边界的时候, 要么"向右走一步", 要么"向下走一步".
  • 如果正在向"右上"走, 优先"向右走一步", 若不能则"向下走一步".
  • 如果正在向"左下"走, 优先"向下走一步", 若不能则"向右走一步".

时间复杂度: O(m*n)

空间复杂度: O(1)

---

参照的思路.

class Solution {public:    /**     * @param matrix: a matrix of integers     * @return: a vector of integers     */    vector
    
      printZMatrix(vector
     
      
        > &matrix) {        vector
       
         v;        if (matrix.size() == 0) return v;        int m = matrix.size(), n = matrix[0].size();        int sum = 0, x = 0, dx = -1;        while (sum < m + n - 1) {            while (x >= 0 && x < m && sum - x >= 0 && sum - x < n) {                v.push_back(matrix[x][sum - x]);                x += dx;            }            x -= dx;            sum++;            if ((dx == -1 && sum - x >= n)            || (dx == 1 && x < m - 1)) {                ++x;            }            dx = -dx;        }        return v;    }};
       
      
     
    

思路:

• 观察下标规律.

(0, 0)(0, 1), (1, 0)(2, 0), (1, 1), (0, 2)(0, 3), (1, 2), (2, 1)(2, 2), (1, 3)(2, 3)

可以看到各行x与y坐标的和是常数, 且该和逐行递增.

• 偶数行x递减, 奇数行x递增.
• 原解法有个缺陷是"矩阵越细长, 空循环就越多". 我的解法对这点进行了优化.
  时间复杂度: O(m*n)
  空间复杂度: O(1)