LC 766. 托普利茨矩阵

题目描述

这是 LeetCode 上的 766. 托普利茨矩阵 ，难度为 简单。

给你一个 m x n 的矩阵 matrix。

如果这个矩阵是托普利茨矩阵，返回 true；否则，返回 false。

如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是托普利茨矩阵。

示例 1：

输入：matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
输出：true
解释：
在上述矩阵中, 其对角线为: 
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]"。 
各条对角线上的所有元素均相同, 因此答案是 True 。

示例 2：

输入：matrix = [[1,2],[2,2]]
输出：false
解释：
对角线 "[1, 2]" 上的元素不同。

提示：

• $m = matrix.length$
• $n == matrix[i].length$
• $1 <= m, n <= 20$
• $0 <= matrix[i][j] <= 99$

进阶：

• 如果矩阵存储在磁盘上，并且内存有限，以至于一次最多只能将矩阵的一行加载到内存中，该怎么办？
• 如果矩阵太大，以至于一次只能将不完整的一行加载到内存中，该怎么办？

---

按「格子」遍历

对于一个合格的「托普利茨矩阵」而言，每个格子总是与其左上角格子相等（如果有的话）。

我们以「格子」为单位进行遍历，每次与左上角的格子进行检查即可。

这样我们每对一个格子进行判断，都要读 matrix 上的两个格子的值（即非边缘格子其实会被读取两次）。

Java 代码：

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] != matrix[i - 1][j - 1]) return false;
            }
        }
        return true;
    }
}

C++ 代码：

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] != matrix[i - 1][j - 1]) return false;
            }
        }
        return true;
    }
};

Python 代码：

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        m, n = len(matrix), len(matrix[0])
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] != matrix[i - 1][j - 1]:
                    return False
        return True

TypeScript 代码：

function isToeplitzMatrix(matrix: number[][]): boolean {
    const m: number = matrix.length, n: number = matrix[0].length;
    for (let i: number = 1; i < m; i++) {
        for (let j: number = 1; j < n; j++) {
            if (matrix[i][j] !== matrix[i - 1][j - 1]) return false;
        }
    }
    return true;
};

• 时间复杂度：$O(n \times m)$
• 空间复杂度：$O(1)$

---

按「线」遍历

如果稍微增加一点点难度：限制每个格子只能被读取一次呢？

这时候我们也可以按照「线」为单位进行检查。

当一条完整的斜线值都相等，我们再对下一条斜线做检查。

这样对于每个格子，我们都是严格只读取一次（如果整个矩阵是存在磁盘中，且不考虑操作系统的按页读取等机制，那么 IO 成本将下降为原来的一半）。

Java 代码：

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int row = m, col = n;
        while (col-- > 0) {
            for (int i = 0, j = col, val = matrix[i++][j++]; i < m && j < n; i++, j++) {
                if (matrix[i][j] != val) return false;
            }
        }
        while (row-- > 0) {
            for (int i = row, j = 0, val = matrix[i++][j++]; i < m && j < n; i++, j++) {
                if (matrix[i][j] != val) return false;
            }
        }
        return true;
    }
}

C++ 代码：

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int row = m, col = n;
        while (col-- > 0) {
            for (int i = 0, j = col, val = matrix[i++][j++]; i < m && j < n; i++, j++) {
                if (matrix[i][j] != val) return false;
            }
        }
        while (row-- > 0) {
            for (int i = row, j = 0, val = matrix[i++][j++]; i < m && j < n; i++, j++) {
                if (matrix[i][j] != val) return false;
            }
        }
        return true;
    }
};

Python 代码：

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        m, n = len(matrix), len(matrix[0])
        row, col = m, n
        while col > 0:
            col -= 1
            i, j, val = 1, col + 1, matrix[0][col]
            while i < m and j < n:
                if matrix[i][j] != val:
                    return False
                i, j = i + 1, j + 1
        while row > 0:
            row -= 1
            i, j, val = row + 1, 1, matrix[row][0]
            while i < m and j < n:
                if matrix[i][j] != val:
                    return False
                i, j = i + 1, j + 1
        return True

TypeScript 代码：

function isToeplitzMatrix(matrix: number[][]): boolean {
    const m = matrix.length, n = matrix[0].length;
    let row = m, col = n;
    while (col-- > 0) {
        for (let i: number = 0, j: number = col, val: number = matrix[i++][j++]; i < m && j < n; i++, j++) {
            if (matrix[i][j] !== val) return false;
        }
    }
    while (row-- > 0) {
        for (let i: number = row, j: number = 0, val: number = matrix[i++][j++]; i < m && j < n; i++, j++) {
            if (matrix[i][j] !== val) return false;
        }
    }
    return true;
};

• 时间复杂度：$O(n \times m)$
• 空间复杂度：$O(1)$

---

进阶

1. 如果矩阵存储在磁盘上，并且内存有限，以至于一次最多只能将矩阵的一行加载到内存中，该怎么办？

使用「背包问题」的一维优化思路：假设我们有装载一行数据大小的内存，每次读取新的行时都进行「从右往左」的覆盖，每次覆盖都与前一个位置的进行比较（其实就是和上一行的左上角位置进行比较）。

如图：

如果你对更多「背包问题」相关内容感兴趣，可以看我这个系列：背包问题&version=13080810&lang=en&nettype=WIFI&ascene=0&fontScale=100)

1. 如果矩阵太大，以至于一次只能将不完整的一行加载到内存中，该怎么办？

将问题看做子问题进行解决：调整读取矩阵的方式（按照垂直方向进行读取）；或使用额外数据记录当前当前片段的行/列数。
更为合理的解决方案是：存储的时候按照「数组」的形式进行存储（行式存储），然后读取的时候计算偏移量直接读取其「左上角」或者「右下角」的值。

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.761 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。