原题
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例:
输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 输出: 4
解法
思想
动态规划：
设dp(x,y)是以matrix[x][y]为右下角的点的最大正方形的边长，则如果matrix[x][y]=='1'，那么dp(x,y)=min(dp(x-1,y-1),dp(x-1,y),dp(x,y-1))。否则dp(x,y)=0
代码
class Solution {
public int maximalSquare(char[][] matrix) {
int height = matrix.length;
if(height == 0) return 0;
int width = matrix[0].length;
int[][] edge = new int[height][width];
int maxEdge = 0;
for(int i = 0 ; i < height;i++){
for(int j = 0;j < width;j++){
if(matrix[i][j] == '0'){
edge[i][j] = 0;
continue;
}
int leftUp = (i == 0 || j == 0) ? 0 : edge[i-1][j-1];
int left = j == 0 ? 0 : edge[i][j-1];
int up = i == 0 ? 0 : edge[i-1][j];
edge[i][j] = Math.min(Math.min(leftUp,left),up) +1;
if(edge[i][j]>maxEdge) maxEdge = edge[i][j];
}
}
return maxEdge*maxEdge;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode221-%e6%9c%80%e5%a4%a7%e6%ad%a3%e6%96%b9%e5%bd%a2/
相关推荐
-
leetcode11-盛最多水的容器
原题 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i,...
-
剑指offer04-二维数组中的查找
原题（来源Leetcode） 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个...
-
leetcode62-不同路径
原题 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Fi...
-
leetcode454-四数相加II
原题 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。 为...
-
剑指offer40-最小的k个数
原题（来源Leetcode） 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 示例 1： ...
-
leetcode124-二叉树中的最大路径和
原题 给定一个非空二叉树，返回其最大路径和。 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。 示例 1: 输入: [1...
-
leetcode206-反转链表
原题 反转一个单链表。 示例： 输入： 1->2->3->4->5->NULL 输出： 5->4->3->2->1->NULL 进阶： 你可以迭代或递归地反转链表。你能否用两种方法...
-
leetcode142-环形链表II
原题 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始...
-
leetcode509-斐波那契数
原题 斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0, F(1) ...
