托普利茨矩阵

难度: Easy

给你一个 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

进阶：

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

Submission

运行时间: 23 ms

内存: 16.0 MB

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
     m, n = len(matrix), len(matrix[0])
    
    # 遍历矩阵中除了最后一行和最后一列的每个元素
     for i in range(m - 1):
        for j in range(n - 1):
            # 检查当前元素是否与其右下角的邻居元素相等
            if matrix[i][j] != matrix[i + 1][j + 1]:
                return False
     return True

Explain

该题解的思路是遍历矩阵中除了最后一行和最后一列的每个元素，对于每个元素，检查它是否与其右下角的邻居元素相等。如果所有元素都满足这个条件，则说明矩阵是托普利茨矩阵，返回 True；否则，返回 False。

时间复杂度: O(mn)

空间复杂度: O(1)

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        m, n = len(matrix), len(matrix[0])
        
        # 遍历矩阵中除了最后一行和最后一列的每个元素
        for i in range(m - 1):
            for j in range(n - 1):
                # 检查当前元素是否与其右下角的邻居元素相等
                if matrix[i][j] != matrix[i + 1][j + 1]:
                    return False
        
        # 如果所有元素都满足条件，返回 True
        return True

Explore

在托普利茨矩阵中，每个元素都应该与其右下角的元素相同（除了最后一列和最后一行的元素，因为它们没有右下角的元素）。这是因为托普利茨矩阵的定义是矩阵中所有的对角线上的元素相同。因此，通过比较每个元素与其右下角的邻居，可以保证这一属性在整个矩阵中得以维持。如果这些比较都相等，那么矩阵就满足托普利茨矩阵的条件。

在检查矩阵是否为托普利茨矩阵时，我们需要比较每个元素与其右下角的元素。然而，矩阵的最后一行和最后一列的元素没有右下角的邻居，因此它们无法进行这样的比较。避免包括这些元素在内的遍历可以防止索引越界的错误，并且这些元素不影响对矩阵是否为托普利茨矩阵的判断。

该方法的时间复杂度为O(m*n)，其中m是矩阵的行数，n是矩阵的列数。这意味着算法的效率与矩阵的大小成正比。对于非常大的矩阵，这种方法可能会消耗较多的时间。然而，考虑到托普利茨矩阵的特性，任何优化方案也需要至少检查矩阵中的大部分元素来保证所有对角线元素的一致性，因此这种方法已经是相对高效的。如果有特定的情况或额外的信息可以利用，可能会有特定的优化方法，但在一般情况下，这种简单的方法是足够有效的。

这种比较方法基于相等性检验，它是通用的，适用于任何可以进行相等性比较的数据类型。对于字符串或对象，只要定义了合适的相等性判断（例如字符串的完全匹配或对象的深度比较），这种方法仍然有效。然而，需要确保所有元素都支持比较操作，且比较逻辑正确地反映了元素间的相等性。