class Solution {
public:
    // 为什么是 m+n-1 条对角线
    // 答：前m条可以看成，每条对角线左下点的会对应新的一行， 总共m行有m 个
    // n-1 列， m条对角线后出现的对角线，每个对角线的左下点对应新的一列 所以有 n-1 列

    // 也可以呃看成n 列  + m-1行, 可以使用右上点对应看 
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        vector<int> ans;

        // i 即代表横纵坐标和, 也代表是第i条对角线
        // 本来总共有m+n-1 条对角线, 由于i从0开始，所以总共有m+n-2条
        for(int i=0; i<m+n-1; i++)
        {
            // 每条对角线只要知道其中一个点就可以推出对角线上所有点

            // 在碰到第m+1 条对角线前，左下的点行值就是对角线的下标
            // 之后 由于最大值就是m-1, 所以是m-1
            int r_left_down = min(i,m-1); 

            // 看成 n 列 + m-1 行 个 对角线
            // 所以右上的列坐标为  min (i, n-1;
            // 所以右上点的行坐标 在前n条对角线为0，
            // 在后m-1 条 右上点的行坐标为 i-(n-1); 
            int r_right_up = max(0,i-(n-1));

            // 代表i为偶数， 遍历方向是从左下到右上
            if(i % 2 == 0)
            {
                for(int x = r_left_down; x>= r_right_up; x--)
                    ans.push_back(mat[x][i-x]);
            }

            // 代表i为奇数，从右上遍历到左下
            else if(i % 2 == 1)
            {
                for(int x = r_right_up; x<=r_left_down ; x++)
                    ans.push_back(mat[x][i-x]);
            } 
        }
        return ans;
    }
};