Skip to content

LeetCode 221. 最大正方形

作者:Choi Yang
更新于:6 个月前
字数统计:396 字
阅读时长:1 分钟
阅读量:

题目描述

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

示例:

javascript
输入:

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 的情况,我们每次求一下它能拓展到的最大边长,然后每次迭代求出结果的最大边长,那么面积就是边长*边长返回即可。

javascript
/**
 * @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; // 返回边长*边长
};
javascript
学如逆水行舟,不进则退

Contributors

Choi Yang