给定一个由 '0' 和 '1' 组成的2维矩阵，返回该矩阵中最大的由 '1' 组成的正方形的面积。输入的矩阵是字符形式而非数字形式。
数据范围：矩阵的长宽满足 
,矩阵中的元素属于 {'1','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; } };