LeetCode 221. 最大正方形

作者:Choi Yang

更新于:7 个月前

字数统计:396 字

阅读时长:1 分钟

题目描述

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximal-square 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

要想求得最大正方形，通过找规律，我们不难发现，对于(i > 0 && j > 0)情况，当前位置边长长度等于左，左上，上三个方向边长长度的最小值，然后加 1，于是我们遍历整个矩阵，对于当前值为 1 的情况，我们每次求一下它能拓展到的最大边长，然后每次迭代求出结果的最大边长，那么面积就是边长*边长返回即可。

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {
  if (!matrix || !matrix.length) return 0;
  let res = 0; // 设置最长边长变量
  let n = matrix.length,
    m = matrix[0].length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (matrix[i][j] == 1) {
        // 对于(i > 0 && j > 0)情况，当前位置边长长度等于左，左上，上三个方向边长长度的最小值，然后加1
        i > 0 &&
          j > 0 &&
          (matrix[i][j] =
            Math.min(matrix[i - 1][j], matrix[i - 1][j - 1], matrix[i][j - 1]) +
            1);
      }
      res = Math.max(res, matrix[i][j]); // 迭代求最长边长
    }
  }
  return res ** 2; // 返回边长*边长
};

学如逆水行舟，不进则退

Contributors

Choi Yang