程序员面试金典 – 面试题 17.23. 最大黑方阵（DP）网络Michael是个半路程序员-

1. 题目

给定一个方阵，其中每个单元(像素)非黑即白。
设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。

返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。
若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。
若无满足条件的子方阵，返回空数组。

matrix.length == matrix[0].length <= 200

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-black-square-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：LeetCode 1139. 最大的以 1 为边界的正方形（DP）

• 求得每个坐标位置处的 上方、左侧 连续的0 有多少个
• 从右下角开始遍历每个位置，每个点的初始边长edge取 min(上、左)
• 检测另外两条边是不是也 >= edge

class Solution { public:     vector<int> findSquare(vector<vector<int>>& mat) { if(mat.size()==0 || mat[0].size() == 0) return {}; int m = mat.size(), n = mat[0].size(), i, j, k;      vector<vector<int>> sumof0Up(m, vector<int>(n,0));//向上连续0个数      vector<vector<int>> sumof0Left(m, vector<int>(n,0));//向左连续0个数 for(i = 0; i < m; i++) { for(j = 0; j < n; j++) { if(mat[i][j] == 0) { if(i==0 && j==0)          sumof0Left[i][j] = 1, sumof0Up[i][j] = 1; else if(i==0 && j>0) {          sumof0Left[i][j] = sumof0Left[i][j-1]+1;          sumof0Up[i][j] = 1; } else if(j==0 && i > 0) {          sumof0Left[i][j] = 1;          sumof0Up[i][j] = sumof0Up[i-1][j]+1; } else {          sumof0Left[i][j] = sumof0Left[i][j-1]+1;          sumof0Up[i][j] = sumof0Up[i-1][j]+1; } } } }      vector<int> ans(3,-1); int edge, x, y; for(i = m-1; i >= 0; i--) { for(j = n-1; j >= 0; --j) {        edge = min(sumof0Up[i][j], sumof0Left[i][j]); //初始边长 while(edge > 0) { if(ans[2] > edge)//肯定小，不必检查了 break;         x = i-edge+1;//上方边的x         y = j-edge+1;//左侧边的y if(sumof0Up[i][y]>=edge && sumof0Left[x][j]>=edge) { //左侧边  上侧边长都大于等 edge if(edge > ans[2]) {           ans[2] = edge;           ans[0] = x;           ans[1] = y; } else if(edge == ans[2] && x <= ans[0]) { if(x < ans[0]) {            ans[0] = x;            ans[1] = y; } else if(x == ans[0] && y < ans[1])            ans[1] = y; } }                     edge--;//遍历所有可能 } } } if(ans[0]==-1) return {}; return ans; } }; 

108 ms 19.2 MB