leetcode-每日一题-No.3142. 判断矩阵是否满足条件

题目

给你一个大小为 m x n 的二维矩阵 grid 。你需要判断每一个格子 grid[i][j] 是否满足：

• 如果它下面的格子存在，那么它需要等于它下面的格子，也就是 grid[i][j] == grid[i + 1][j] 。

• 如果它右边的格子存在，那么它需要不等于它右边的格子，也就是 grid[i][j] != grid[i][j + 1] 。

如果 所有 格子都满足以上条件，那么返回 true ，否则返回 false 。

示例 1：

输入：grid = [[1,0,2],[1,0,2]]

输出：true

解释：

网格图中所有格子都符合条件。

示例 2：

输入：grid = [[1,1,1],[0,0,0]]

输出：false

解释：

同一行中的格子值都相等。

示例 3：

输入：grid = [[1],[2],[3]]

输出：false

解释：

同一列中的格子值不相等。

提示：

• 1 <= n, m <= 10

• 0 <= grid[i][j] <= 9

答案代码

class Solution(object):
    def satisfiesConditions(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: bool
        """
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i + 1 < len(grid) and grid[i][j] != grid[i + 1][j]:
                    return False
                if j + 1 < len(grid[0]) and grid[i][j] == grid[i][j + 1]:
                    return False
        return True


if __name__ == '__main__':
    grid = [[1, 0, 2], [1, 0, 2]]
    print(Solution().satisfiesConditions(grid))
    grid = [[1, 1, 1], [0, 0, 0]]
    print(Solution().satisfiesConditions(grid))
    grid = [[1], [2], [3]]
    print(Solution().satisfiesConditions(grid))
    grid = [[0]]
    print(Solution().satisfiesConditions(grid))

结果分析

代码复杂度分析

这段代码的时间复杂度和空间复杂度分析如下：

时间复杂度

主循环: 有两个嵌套的 for 循环，分别遍历 grid 的行和列，因此基本操作（即条件判断）的次数为 O(mn)，其中 m 是 grid 的行数，n 是 grid 的列数。

条件判断: 每个条件判断内部的操作都是常数时间的操作（如索引访问和比较），因此这部分的时间复杂度也为 (O(1))。

综合来看，整个函数的时间复杂度为 O(mn)。

空间复杂度

函数内部没有使用额外的数据结构来存储数据，只使用了几个临时变量（如 i, j）来进行索引操作。

因此，空间复杂度为 O(1)，即常数级别。

总结：该函数的时间复杂度为 O(mn)，空间复杂度为 O(1)。