# subject ：

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

For example, given the following matrix:

```1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
```

Return 4.

Topic link ：https://leetcode.com/problems/maximal-square/.

This question is a bit similar ：LeetCode OJ And Maximal Rectangle （ Largest rectangle ）. But the solution is totally different .

# Ideas ：

Dynamic programming . set up f[i][j] Represents the maximum length of the square containing the current point , There is a recurrence relation, such as the following ：

```f[j] = matrix[j]
f[i] = matrix[i]
For i > 0 and j > 0:
if matrix[i][j] = 0, f[i][j] = 0;
if matrix[i][j] = 1, f[i][j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1.```

# Code 1：

```class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix)
{
int row = matrix.size();
if(row == 0)
return 0;
int col = matrix.size();
vector<vector<int> > f(row , vector<int>(col , 0));
int maxsize = 0;    // Maximum side length
for(int i = 0 ; i < row ; i++)
{
for(int j = 0 ; j < col ; j++)
{
if(i == 0 || j == 0)
f[i][j] = matrix[i][j]-'0';
else
{
if(matrix[i][j] == '0')
f[i][j] = 0;
else
f[i][j] = min(min(f[i-1][j] , f[i][j-1]) , f[i-1][j-1]) + 1;
}
maxsize = max(maxsize , f[i][j]);
}
}
return maxsize * maxsize;
}

};```

# Code 2：

The optimization space is one dimension

```class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix)
{
int row = matrix.size();
if(row == 0)
return 0;
int col = matrix.size();

vector<int> f(col , 0);

int tmp1 = 0 , tmp2 = 0;

int maxsize = 0;    // Maximum side length
for(int i = 0 ; i < row ; i++)
{
for(int j = 0 ; j < col ; j++)
{
tmp1 = f[j];    //tmp1 Put the present f[j] Save the following , For the next inference f[i+1][j+1] Top left corner of f[i-1][j-1]
if(i == 0 || j == 0)
f[j] = matrix[i][j]-'0';
else
{
if(matrix[i][j] == '0')
f[j] = 0;
else
f[j] = min(min(f[j-1] , f[j]) , tmp2) + 1;  // there tmp2 That's the code 1 Of f[i-1][j-1]
}
tmp2 = tmp1 ;   // hold tmp1 Assign to tmp2, For next time for Circular search f[j+1]
maxsize = max(maxsize , f[j]);
}
}
return maxsize * maxsize;
}

};```

## LeetCode OJ And Maximal Square （ The largest square ） More articles about

1. LeetCode OJ：Maximal Square（ The largest rectangle ）

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and ret ...

2. 【LeetCode】221. Maximal Square

Maximal Square Given a 2D binary matrix filled with 0's and 1's, find the largest square containing ...

3. 50.Maximal Square（ The largest square ）

Level   Medium Title Description : Given a 2D binary matrix filled with 0's and 1's, find the largest square conta ...

4. 【LeetCode 221】Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and ret ...

5. LeetCode OJ：Maximal Rectangle（ The largest rectangle ）

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and ...

6. LeetCode OJ 85. Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and ...

7. Find the maximum square area — leetcode 221. Maximal Square

I wanted to be like Yuanyou , Write a summary farewell 2015, Or say goodbye to the passing year of the sheep , But what happened in the past year , It's really beyond the imagination of ordinary people , It's not representative either , So the plan is this year 6 Write an article in September " Half year summary " ...

8. [LintCode] Maximal Square The largest square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and ret ...

9. leetcode How to solve problems everyday 221 Maximal Square

Problem description : Topic link :221 Maximal Square The solution to the problem is to give a M*N Matrix , Only '1', '0', Two elements : You need to find out from '1' The largest square of the composition . Okay , this is it . We see ...

## Random recommendation

1. Chapter two TP-Link 703N OpenWrt Brush back the original firmware

(TP Official website ) First, download the original firmware Use terminal , Use cat /proc/mtd View the upgrade commands supported by routing , My is root@OpenWrt:~# cat /proc/mtd dev:    size   erases ...

2. spring in @param and mybatis in @param Use difference

spring in @param /** * Query whether the specified user and enterprise have configured roles * @param businessId memberId * @return */ int selectRoleCount ...

3. VirtualBox Create a virtual computer 、 perform Genymotion The simulator reported an error

When installed Genynition About Android After debugging the simulator for the application , stay Genymotion Execution platform virtualBox:VirtualBox Create a virtual computer . perform Genymotion The simulator reported an error : Misselling ...

4. SQLite senior ： One database builds multiple tables , Wrapper class

package eoe.database; import android.content.Context; import android.database.sqlite.SQLiteDatabase; ...

5. C# Multithreading timeout processing practice in

Recently I've been dealing with C# About China timeout Some aspects of behavior bug. The solution is very interesting , So I'm here to share with you . I want to deal with the following situations : We made an application , There is a module in the program , Its function is to show the user a ...

6. django-rest-framework Class based view of

Preface : In the last blog post , It's mainly about requests and responses , Inside the project views.py The view functions in are all function based , And we introduced @api_view This is a very useful decorator . meanwhile , We also introduced APIView This class , But I haven't used it yet ...

7. Java Constructors and the use of constructors

We're in the process of building normal classes , There may be a lot of problems , Scalability . Security and so on . Imagine , Such a scene , Now we're going to create a class , Among them is 6 Attributes , Among them are 4 The value of a property is not very certain ( Maybe an object doesn't need one of its values ), ...

8. azkaban Comparison of workflow scheduler and related tools

Reprinted from : Workflow scheduler azkaban, It is mainly used for architecture selection , Please refer to :Azkaban Installation and introduction ,azkaban Simple use Why do we need a workflow scheduling system A complete data analysis system is usually composed of a large number of task units : ...

9. 20165305 Experiment 1 ： Java Familiarity with development environment

experiment 1-1 establish " My student number exp1" The catalog of . stay " My student number exp1" Create under directory src,bin Such as catalog . javac,java Execution in " My student number exp1& ...

10. centos7.3 Fast installation mariadb（mysql）

From the latest version of linux The system starts , The default is Mariadb instead of mysql! Use the system's own repos Easy to install : yum install mariadb mariadb-server systemct ...