前言
新的一年，好好学习。
正文
问题来源
本问题来自leetcode上的221题。
问题描述
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例 1：
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
分析：
思想和我去年做的leetcode85一致。
func max_f(a, b int) int {
if a > b {
return a
}
return b
}
func min_f(a, b int) int {
if a < b {
return a
}
return b
}
func maximalSquare(matrix [][]byte) int {
rlen := len(matrix)
if rlen == 0 {
return 0
}
clen := len(matrix[0])
height := make([]int, clen)
left := make([]int, clen)
right := make([]int, clen)
for j := 0; j < clen; j++ {
right[j] = clen
}
var lstart, rstart, max int
for i := 0; i < rlen; i++ {
lstart, rstart = 0, clen
for j := 0; j < clen; j++ {
if matrix[i][j] == '0' {
left[j] = 0
lstart = j + 1
} else {
left[j] = max_f(lstart, left[j])
}
}
for j := clen - 1; j >= 0; j-- {
if matrix[i][j] == '0' {
right[j] = clen
rstart = j
} else {
right[j] = min_f(rstart, right[j])
}
}
for j := 0; j < clen; j++ {
if matrix[i][j] == '0' {
height[j] = 0
} else {
height[j]++
if height[j] <= right[j] - left[j] && height[j]*height[j] > max {
max = height[j]*height[j]
}
}
}
}
return max
}
后来看到别人的解答，发现没必要弄的这么复杂
class Solution {
public int maximalSquare(char[][] matrix) {
/**
dp[i][j]表示以第i行第j列为右下角所能构成的最大正方形边长, 则递推式为:
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
**/
int m = matrix.length;
if(m < 1) return 0;
int n = matrix[0].length;
int max = 0;
int[][] dp = new int[m+1][n+1];
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
if(matrix[i-1][j-1] == '1') {
dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
max = Math.max(max, dp[i][j]);
}
}
}
return max*max;
}
}
总结：
勤思考。
结语
不管怎么样好好加油。
