221.最大正方形

链接：221.最大正方形
难度：Medium
标签：数组、动态规划、矩阵
简介：在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

题解 1 - javascript

• 编辑时间：2020-05-08
• 执行用时：440ms
• 内存消耗：74.3MB
• 编程语言：javascript
• 解法介绍：先把字符串转换为后缀表达式，然后再利用栈计算。

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {
  function isAllOne(i, j) {
    let b = false;
    try {
      b = matrix[i + 1][j + 1] === '1' && matrix[i][j + 1] === '1' && matrix[i + 1][j] === '1';
    } catch (error) {}
    return b;
  }
  let max = 0;
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      if (matrix[i][j] === '0') continue;
      let width = 1;
      let size = 1;
      let temp = [];
      const queue = [[i, j]];
      while (queue.length !== 0) {
        const [nextI, nextJ] = queue.shift();
        if (!isAllOne(nextI, nextJ)) break;
        temp.push([nextI, nextJ + 1], [nextI + 1, nextJ], [nextI + 1, nextJ + 1]);
        if (--size === 0) {
          queue.push(...temp);
          size = temp.length;
          temp.length = 0;
          width++;
        }
      }
      max = Math.max(max, width);
    }
  }
  return max ** 2;
};