Easy

题目描述

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

解题思路

这道题要求检查网格是否满足两个条件：

  1. 垂直相同：每个单元格必须与其下方的单元格值相同
  2. 水平不同：每个单元格必须与其右侧的单元格值不同

解题思路

根据题目提示，我们可以采用两步验证法：

第一步：检查每列内部值是否相同

  • 遍历每一列，确保该列中所有元素都相等
  • 这样保证了垂直方向的条件

第二步：检查相邻列之间值是否不同

  • 由于第一步已确保每列内部值相同，我们只需比较相邻列的第一行元素
  • 如果第一行相邻元素不同，则整列都不同

这种方法的优势是：

  • 逻辑清晰，分别处理两个条件
  • 时间复杂度优化，不需要检查每个单元格与右侧的关系
  • 代码简洁易懂

推荐解法：两步验证法，先检查列内一致性，再检查列间差异性。

代码实现

class Solution {
public:
    bool satisfiesConditions(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 检查每列内部值是否相同
        for (int j = 0; j < n; j++) {
            for (int i = 1; i < m; i++) {
                if (grid[i][j] != grid[0][j]) {
                    return false;
                }
            }
        }
        
        // 检查相邻列之间值是否不同
        for (int j = 0; j < n - 1; j++) {
            if (grid[0][j] == grid[0][j + 1]) {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def satisfiesConditions(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        
        # 检查每列内部值是否相同
        for j in range(n):
            for i in range(1, m):
                if grid[i][j] != grid[0][j]:
                    return False
        
        # 检查相邻列之间值是否不同
        for j in range(n - 1):
            if grid[0][j] == grid[0][j + 1]:
                return False
        
        return True

public class Solution {
    public bool SatisfiesConditions(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        // 检查每列内部值是否相同
        for (int j = 0; j < n; j++) {
            for (int i = 1; i < m; i++) {
                if (grid[i][j] != grid[0][j]) {
                    return false;
                }
            }
        }
        
        // 检查相邻列之间值是否不同
        for (int j = 0; j < n - 1; j++) {
            if (grid[0][j] == grid[0][j + 1]) {
                return false;
            }
        }
        
        return true;
    }
}

/**
 * @param {number[][]} grid
 * @return {boolean}
 */
var satisfiesConditions = function(grid) {
    const m = grid.length, n = grid[0].length;
    
    // 检查每列内部值是否相同
    for (let j = 0; j < n; j++) {
        for (let i = 1; i < m; i++) {
            if (grid[i][j] !== grid[0][j]) {
                return false;
            }
        }
    }
    
    // 检查相邻列之间值是否不同
    for (let j = 0; j < n - 1; j++) {
        if (grid[0][j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n)
空间复杂度O(1)

说明：

  • 时间复杂度：需要遍历整个网格一次来检查列内一致性，再遍历第一行来检查列间差异性
  • 空间复杂度：只使用了常数级别的额外空间

相关题目