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 上的两个格子的值（即非边缘格子其实会被读取两次）。

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;
    }
}

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

---

按「线」遍历

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

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

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

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

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;
    }
}

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

---

进阶

1. 如果矩阵存储在磁盘上，并且内存有限，以至于一次最多只能将矩阵的一行加载到内存中，该怎么办？
   使用「背包问题」的一维优化思路：假设我们有装载一行数据大小的内存，每次读取新的行时都进行「从右往左」的覆盖，每次覆盖都与前一个位置的进行比较（其实就是和上一行的左上角位置进行比较）。

如图：

如果你对更多「背包问题」相关内容感兴趣，可以看我这篇总结：深度讲解背包问题

1. 如果矩阵太大，以至于一次只能将不完整的一行加载到内存中，该怎么办？
   亲，这边建议升级内存，啊呸 …
   将问题看做子问题进行解决：调整读取矩阵的方式（按照垂直方向进行读取）；或使用额外数据记录当前当前片段的行/列数。
   更为合理的解决方案是：存储的时候按照「数组」的形式进行存储（行式存储），然后读取的时候计算偏移量直接读取其「左上角」或者「右下角」的值。

---

最后

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

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

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

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