[leetcode] 221. Maximal Square

[leetcode] 221. Maximal Square

Description

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

Input: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0Output: 4

分析

题目的意思是：找出一个二维数组上最大的只包含1的正方形。

把数组中每一个点都当成正方形的左顶点来向右下方扫描，来寻找最大正方形。具体的扫描方法是，确定了左顶点后，再往下扫的时候，正方形的竖边长度就确定了，只需要找到横边即可，这时候我们使用直方图的原理，从其累加值能反映出上面的值是否全为1。

例如题目的那个例子： round 1:

1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0

step 1

1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0 v=1,0,1,0,0

step 2

1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0 v=2,0,2,1,1

step 3

1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0 v=3,1,3,2,2

step 4

1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0 v=4,1,3,3,2

round 2 …

代码

class Solution {public: int maximalSquare(vector>& matrix) { int res=0; for(int i=0;i v(matrix[i].size(),0); for(int j=i;j &v,int k){ if(v.size()

参考文献

​​[LeetCode] Maximal Square 最大正方形​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。