1139. Largest 1-Bordered Square

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation