题目描述
这是 LeetCode 上的 766. 托普利茨矩阵 ，难度为 简单。
Tag : 「模拟」
给你一个 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(n∗m)
- 空间复杂度：O(1)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(n∗m)
- 空间复杂度：O(1)O(1)
进阶
- 如果矩阵存储在磁盘上，并且内存有限，以至于一次最多只能将矩阵的一行加载到内存中，该怎么办？
使用「背包问题」的一维优化思路：假设我们有装载一行数据大小的内存，每次读取新的行时都进行「从右往左」的覆盖，每次覆盖都与前一个位置的进行比较（其实就是和上一行的左上角位置进行比较）。
如图：
如果你对更多「背包问题」相关内容感兴趣，可以看我这篇总结：深度讲解背包问题
- 如果矩阵太大，以至于一次只能将不完整的一行加载到内存中，该怎么办？
亲，这边建议升级内存，啊呸 ... 将问题看做子问题进行解决：调整读取矩阵的方式（按照垂直方向进行读取）；或使用额外数据记录当前当前片段的行/列数。 更为合理的解决方案是：存储的时候按照「数组」的形式进行存储（行式存储），然后读取的时候计算偏移量直接读取其「左上角」或者「右下角」的值。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.761 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
