[LeetCode] 1139. Largest 1-Bordered Square

[grandyang]

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn't exist in the grid.

Example 1:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

Example 2:

Input: grid = [[1,1,0,0]]
Output: 1

Constraints:

• 1 <= grid.length <= 100
• 1 <= grid[0].length <= 100
• grid[i][j] is 0 or 1

这道题给了一个只有0和1的二维数组 grid，现在让找出边长均为1的最大正方形的元素个数，实际上就是这个正方形的面积，也就是边长的平方。给定的 grid 不一定是个正方形，首先来想，如何确定一个正方形，由于边长的是相同的，只要知道了边长，和其中的一个顶点，那么这个正方形也就确定了。如何才能快速的知道其边长是否均为1呢，每次都一个一个的遍历检查的确太不高效了，比较好的方法是统计连续1的个数，注意这里不是累加和数组，而且到当前位置为止的连续1的个数，需要分为两个方向，水平和竖直。这里用 left 表示水平，top 表示竖直。若 left[i][j] 为k，则表示从 grid[i][j-k] 到 grid[i][j] 的数字均为1，同理，若 top[i][j] 为k，则表示 grid[i-k][j] 到 grid[i][j] 的数字均为1，则表示找到了一个边长为k的正方形。由于 grid 不一定是正方形，那么其可以包含的最大的正方形的边长为 grid 的长和宽中的较小值。边长确定了，只要遍历左上顶点的就行了，然后通过连续1数组 top 和 left 来快速判断四条边是否为1，只要找到了这个正方形，就可以直接返回了，否则就将边长减少1，继续查找，参见代码如下：

解法一：

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> left(m, vector<int>(n)), top(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) continue;
                left[i][j] = j == 0 ? 1 : left[i][j - 1] + 1;
                top[i][j] = i == 0 ? 1 : top[i - 1][j] + 1;
            }
        }
        for (int len = min(m, n); len > 0; --len) {
            for (int i = 0; i < m - len + 1; ++i) {
                for (int j = 0; j < n - len + 1; ++j) {
                    if (top[i + len - 1][j] >= len && top[i + len - 1][j + len - 1] >= len && left[i][j + len - 1] >= len && left[i + len - 1][j + len - 1] >= len) return len * len;
                }
            }
        }
        return 0;
    }
};

上面的方法是根据边长进行遍历，若数组很大，而其中的1很少，这种遍历方法将不是很高效。我们从 grid 数组的右下角往左上角遍历，即从每个潜在的正方形的右下角开始遍历，根据右下顶点的位置取到的 top 和 lef 值，分别是正方形的右边和下边的边长，取其中较小的那个为目标正方形的边长，然后现在就要确定是否存在相应的左边和上边，存在话的更新 mx，否则将目标边长减1，继续查找，直到目标边长小于 mx 了停止。继续这样的操作直至遍历完所有的右下顶点，这种遍历的方法要高效不少，参见代码如下：

解法二：

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int mx = 0, m = grid.size(), n = grid[0].size();
        vector<vector<int>> left(m, vector<int>(n)), top(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) continue;
                left[i][j] = j == 0 ? 1 : left[i][j - 1] + 1;
                top[i][j] = i == 0 ? 1 : top[i - 1][j] + 1;
            }
        }
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                int small = min(left[i][j], top[i][j]);
                while (small > mx) {
                    if (top[i][j - small + 1] >= small && left[i - small + 1][j] >= small) mx = small;
                    --small;
                }
            }
        }
        return mx * mx;
    }
};

Github 同步地址:

#1139

参考资料：

https://leetcode.com/problems/largest-1-bordered-square/

https://leetcode.com/problems/largest-1-bordered-square/discuss/345233/JavaC%2B%2BPython-Straight-Forward

https://leetcode.com/problems/largest-1-bordered-square/discuss/345265/c%2B%2B-beats-100-(both-time-and-memory)-concise-with-algorithm-and-image

LeetCode All in One 题目讲解汇总(持续更新中...)