LeetCode:Maximal Square浅析
Maximal Square
Total Accepted:25468Total Submissions:110270Difficulty:Medium
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 0Return 4.
Credits:
Special thanks to@Freezenfor adding this problem and creating all test cases.
Subscribeto see which companies asked this question
Hide Tags
Dynamic Programming
Hide Similar Problems
(H) Maximal Rectangle
思路:
1.动态规划的题,可以维护一个ret[m*n]的整数数组去表示matrix各元素的状态;
2.首先边界i=0,j=0:第一行和第一列与matrix相同(即ret[i][0] = matrix[i][0],ret[0][i] = matrix[0][i]);
3.当i>0,j>0时,
如果matrix[i][j]=='0',ret[i][j]=0;
如果matrix[i][j]=='1',ret[i][j]由左上角的3个值推出;
推导公式,即状态转移方程为:ret[i][j]=min(ret[i-1][j],ret[i][j-1],ret[i-1][j-1]) + 1;
code:
class Solution { public: int maximalSquare(vector>& matrix) { int m = matrix.size(); if(m==0) return 0; int n = matrix[0].size(); vector> ret(m, vector(n,0)); int maxSize = 0; for(int i=0;i
当然还可以有一些空间上的优化:Easy DP solution in C++ with detailed explanations (8ms, O(n^2) time and O(n) space)
下一篇: stm32学习笔记 串口usart
推荐阅读
-
LeetCode:Two Sum浅析
-
leetcode 85. Maximal Rectangle(最大全1子矩阵)
-
LeetCode:Maximal Square浅析
-
【leetcode】633. Sum of Square Numbers(Python & C++)
-
LeetCode:Two Sum浅析
-
【leetcode】633. Sum of Square Numbers(Python & C++)
-
leetcode-221. Maximal Square 最大正方形
-
Leetcode—221.Maximal Square 最大正方形
-
LeetCode:Maximal Square浅析