给定一个由 '0' 和 '1' 组成的2维矩阵，返回该矩阵中最大的由 '1' 组成的正方形的面积。输入的矩阵是字符形式而非数字形式。
数据范围：矩阵的长宽满足 
,矩阵中的元素属于 {'1','0'}
进阶：空间复杂度 )
， 时间复杂度
[编程题]最大正方形
单调栈
public int solve (char[][] matrix) {
if(matrix == null || matrix.length == 0) return 0;
Stack<Integer> stack = new Stack<>();
int maxRes = 0;
int m = matrix.length, n = matrix[0].length;
int[] arr = new int[n+2];
for(int i = 0; i < m; i++){
stack.push(0);
for(int j = 1; j < n+2; j++){
if(j < n+1){
if(matrix[i][j-1] == '1'){
arr[j]++;
}else{
arr[j] = 0;
}
}
while(!stack.isEmpty() && arr[stack.peek()] > arr[j]){
int length = Math.min(arr[stack.pop()], j-stack.peek()-1);
maxRes = Math.max(maxRes, length);
}
stack.push(j);
}
while(!stack.isEmpty()) stack.pop();
}
return maxRes*maxRes;
} public int solve (char[][] matrix) {
if(matrix == null || matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[][] dp = new int[m+1][n+1];
int max = 0;
for(int i = 1; i < m+1; i++){
for(int j = 1; j < n+1; j++){
if(matrix[i-1][j-1] == '1'){
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
max = Math.max(max, dp[i][j]);
}
}
}
return max*max;
}
发表于 2021-10-16 16:12:30
回复(0)
用char数组真的很反人类的出题，想必是copy某Code的题目...
思路就是动态规划，遇到为1的处理一下。
转移方程为：dp(x, y) = min {dp(x-1, y), dp(x, y-1), dp(x-1, y-1)} + 1
public class Solution {
public int solve (char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] dp = new int[m+1][n+1];
int max = Math.max(0, matrix[0][0] - 48);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i-1][j-1] == '1') {
dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
max = Math.max(max, dp[i][j]);
}
}
}
return max * max;
}
}
发表于 2021-08-10 11:24:09
回复(0)
public int solve (char[][] matrix) {
//以[i,j]位置为右下角的正方形取决于它所在的左、上、左上位置所能组成的最大正方形的周长。
//如果[i,j]=0，那么就不可能组成正方形
int m=matrix.length;
int n=matrix[0].length;
int [][]dp=new int[m][n];
int side=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]=='0')
dp[i][j]=0;
else{
if(i==0||j==0) dp[i][j]=1;//边界上只能凑成边长为1的正方形
else dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
}
side=Math.max(side,dp[i][j]);
}
}
return side*side;
}
发表于 2021-03-26 18:37:50
回复(0)
import java.util.*;
public class Solution {
/**
* 最大正方形
* @param matrix char字符型二维数组
* @return int整型
*/
public int solve (char[][] matrix) {
// write code here
int area = 0;
int rows = matrix.length;
int cols = matrix[0].length;
int[][] dp = new int[rows+1][cols+1];
for(int i=1; i<=rows; i++){
for(int j=1; j<=cols; j++){
if(matrix[i-1][j-1] == '1'){
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j])) +1;
area = Math.max(area, dp[i][j]*dp[i][j]);
}
}
}
return area;
}
}
动态规划算法
发表于 2021-03-11 07:47:43
回复(0)
大概思路是想象一个方块在移动，从最可能最大的方块开始检测和移动；检测过程：如果方块中任意有一个值为0，则不是方块，则让方块边数-1，然后接着从头开始检测和移动。
import java.util.*;
public class Solution {
/**
* 最大正方形
* @param matrix char字符型二维数组
* @return int整型
*/
//检测过程 如果在方块内部有任意一个值为0 则不构成方块
public boolean checkQ(char[][] a, int i, int j, int k){
int m = a.length;
int n = a[0].length;
for(int p=0;p<k;p++){
for(int q=0;q<k;q++){
if(a[i+p][j+q] == 0 || a[i+p][j+q] == '0'){
return false;
}
}
}
return true;
}
public int solve (char[][] matrix) {
// write code here
int m = matrix.length;
int n = matrix[0].length;
char[][] a = matrix;
char[][] temp = new char[n][m];
if(m > n){
//为了方便 统一将方块转换为列大于行，对二维数组进行一个翻转
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
temp[j][i] = matrix[i][j];
}
}
a = temp;
}
//开始从最大的方块检测
for(int k=m;k>0;k--){
//移动方块列的位置
for(int i=0;i<m-k+1;i++){
//移动方块行的位置
for(int j=0;j<n-k+1;j++){
//检测
boolean flag = checkQ(a, i, j, k);
if(flag == true){
return k*k;
}
}
}
}
return 1;
}
}
发表于 2021-01-02 16:47:57
回复(0)
Java描述
import java.util.*;
public class Solution {
/**
* 最大正方形
* @param matrix char字符型二维数组
* @return int整型
*/
public int solve (char[][] matrix) {
// write code here
if(matrix == null){return 0;}
int m = matrix.length;
int n = matrix[0].length;
int res = 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] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]),
dp[i - 1][j - 1]) + 1;
res = Math.max(res, dp[i][j]);
}
}
}
return res * res;
}
}
发表于 2020-12-14 23:19:36
回复(0)
import java.util.*;
public class Solution {
/**
* 最大正方形
* @param matrix char字符型二维数组
* @return int整型
*/
public int solve (char[][] matrix) {
// write code here
if (matrix.length == 1 && matrix[0].length == 1) {
return matrix[0][0] - 48;
}
if (matrix.length == 0) {
return 0;
}
int ans = Integer.MIN_VALUE;
int m = matrix.length, n = matrix[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
continue;
}
if (matrix[i][j] == '1') {
int temp = Math.min(matrix[i][j - 1] - 48, matrix[i - 1][j] - 48);
temp = Math.min(temp, matrix[i - 1][j - 1] - 48) + 1;
matrix[i][j] = (char)(48 + temp);
if (ans < temp) {
ans = temp;
}
}
}
}
return ans * ans;
}
}
发表于 2020-09-07 14:12:10
回复(0)
动态规划关键是找出转移方程：
以当前顶点作为正方形的右下顶点，找出左边前一个顶点，左上前一个顶点，右上前一个顶点，三个值的最小边；得出转移方程：
dp[i][j] = min{dp[i-1][j-1]，dp[i-1][j]，dp[i][j-1]} + 1
import java.util.*;
public class Solution {
/**
* 最大正方形
* @param matrix char字符型二维数组
* @return int整型
*/
public int solve (char[][] matrix) {
// write code here
if(matrix.length==0||matrix[0].length==0) {
return 0;
}
int m = matrix.length;
int n = matrix[0].length;
int max = 0;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) { //将字符数组变为整形数组
for (int j = 0; j < n ; j++) {
dp[i][j] = matrix[i][j]-'0';
if (dp[i][j] == 1) {
max = 1;
}
}
}
for(int i = 1;i<m; i++){
for(int j = 1;j<n; j++){
if(matrix[i][j]=='1'){
// (i, j) 为正方形右下顶点，对比小单位正方形左下顶点（i, j-1）, 左上顶点（i-1， j-1），右上顶点(i-1, j)的最小值（正方形边）
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
max = Math.max(dp[i][j], max);
}
}
}
return max*max;
}
}
编辑于 2020-08-27 10:42:51
回复(0)
import java.util.*;
public class Solution {
/**
* 最大正方形
* @param matrix char字符型二维数组
* @return int整型
*/
public int solve (char[][] matrix) {
// write code here
int [][]dp = new int[matrix.length][matrix[0].length];
int bc = 0;
dp[0][0]=0;
for(int i=0;i<dp.length;i++){
dp[i][0]=matrix[i][0]-'0';
}
for(int j=0;j<dp[0].length;j++){
dp[0][j]=matrix[0][j]-'0';
}
for(int i=1;i<dp.length;i++){
for(int j=1;j<dp[0].length;j++){
if(matrix[i][j]=='0'){
dp[i][j]=0;
}else{
int up = dp[i-1][j];
int left = dp[i][j-1];
int ul = dp[i-1][j-1];
if(up==left && up==ul){
dp[i][j]=up+1;
}else{
int m = Math.min(up,Math.min(left,ul));
dp[i][j]=m+1;
}
}
}
}
for(int i=0;i<dp.length;i++){
for(int j=0;j<dp[0].length;j++){
bc = Math.max(bc,dp[i][j]);
}
}
int area = bc*bc;
return area;
}
} 前排提示：这道题有个很坑的地方，java输入的matrix是字符型。自测的时候算出来面积两千多，一直不知道啥问题，一看函数参数列表......
发表于 2020-08-25 17:10:52
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-12-25 14:01:51
-
2022-11-12 19:32:05 -
2022-09-16 16:25:46
-
2022-09-16 12:08:04 -
2022-09-14 20:36:11
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
用dp[i][j]表示以matrix[i][j]为右下角的全为1组成的最大正方形的边长，则:
1. 若matrix[i][j] == 0, 则dp[i][j] = 0
2. 若matrix[i][j] == 1, 则dp[i][j] = min{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]} + 1
原因可以看下面这张图:
class Solution { public: /** * 最大正方形 * @param matrix char字符型vector<vector<>> * @return int整型 */ int solve(vector<vector<char> >& matrix) { if(matrix.size()==0 || matrix[0].size()==0) { return 0; } int Rows = matrix.size(), Cols = matrix[0].size(); vector<vector<int>> dp(Rows, vector<int>(Cols, 0)); int maxSide = 0; for(int i = 0; i < Rows; i++) { for(int j = 0; j < Cols; j++) { if(matrix[i][j] == '1') { if(i==0 || j==0) { dp[i][j] = 1; } else { dp[i][j] = std::min(std::min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1; } } maxSide = std::max(maxSide, dp[i][j]); } } return (long long)maxSide * maxSide; } };