题目描述（中等难度）

输出包含的最大正方形面积。

解法一暴力

参考解法一，85 题是求包含 1 的最大矩形，这道题明显只是 85 题的一个子问题了，85 题的解法稍加修改就能写出这道题了，下边讲一下 85 题的思路。

参考-solution-for-your-reference>)，遍历每个点，求以这个点为矩阵右下角的所有矩阵面积。如下图的两个例子，橙色是当前遍历的点，然后虚线框圈出的矩阵是其中一个矩阵。

怎么找出这样的矩阵呢？如下图，如果我们知道了以这个点结尾的连续 1 的个数的话，问题就变得简单了。

然后向上扩展一行，高度增加一，选出当前列最小的数字，作为矩阵的宽，如上图，当前列中有 2 和 4 ，那么就将 2 作为矩形的宽，求出面积，对应上图的矩形圈出的部分。

按照上边的方法，遍历所有的点，以当前点为矩阵的右下角，求出所有的矩阵就可以了。下图是某一个点的过程。

以橙色的点为右下角，高度为 1。

高度为 2。

高度为 3。

下边是 85 题的代码。

我们先在上边的代码基础上，把这道题做出来，我把修改的地方标记出来了。下边的代码一定程度上已经做了一些优化，把能提前结束的地方提前结束了。

当然因为我们只考虑正方形，我们可以抛开原来的代码，只参照之前的思路写一个新的代码。

首先因为正方形的面积是边长乘边长，所以上边的是没有意义的，我们只记录最大边长即可。然后是其它细节的修改，让代码更简洁，代码如下。

写出解法一，也没有往别的地方想了，参考这里，很典型的动态规划的问题了。

解法一中我们求每个点的最大边长时，没有考虑到之前的解，事实上之前的解完全可以充分利用。

用 dp[i][j] 表示以 matrix[i][j] 为右下角正方形的最大边长。那么递推式如下。

初始条件，那就是第一行和第一列的 dp[i][j] = matrix[i][j] - '0'，也就意味着 dp[i][j] 要么是 0 要么是 1。

然后就是递推式。

dp[i][j] = Min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1。

也就是当前点的左边，上边，左上角的三个点中选一个最小值，然后加。

首先要明确 dp[i][j] 表示以 matrix[i][j] 为右下角的正方形的最大边长。

然后我们从当前点向左和向上扩展，可以参考下边的图。

向左最多能扩展多少呢？dp[i][j-1] 和 dp[i-1][j-1]，当前点左边和左上角选一个较小的。也就是它左边最大的正方形和它左上角最大的正方形的，边长选较小的。

向上能能扩展多少呢？dp[i-1][j] 和 dp[i-1][j-1]，当前点上边和左上角选一个较小的。也就是它上边最大的正方形和它左上角最大的正方形，边长选较小的。

然后向左扩展和向上扩展两个最小值中再选一个较小的，最后加上 1 就是最终的边长了。

最终其实是从三个正方形中最小的边长。

代码的话，使用个技巧，那就是行和列多申请一行，这样的话第一行和第一列的情况就不需要单独考虑了。

然后又是动态规划的经典操作了，空间复杂度的优化，之前也遇到很多了，这里不细讲了。因为更新当前行的时候，只用到前一行的信息，之前的行就没有再用到了，所以我们可以用一维数组，不需要二维矩阵。

把图画出来就可以理解出来各个变量的关系了，这里偷懒就不画了。第一次遇到空间复杂度的优化是，写的比较详细，大家可以看看。后边基本上遇到动态规划，就会考虑空间复杂度的优化，很多很多了。可以在 https://leetcode.wang/ 搜索动态规划做一做。

下边是空间复杂度优化的代码，最关键的是用保存了左上角的值。

解法一的话是受之前解法的启发，解法二的话算是动态规划的经典应用了，通过之前的解更新当前的解。这里的空间复杂度优化需要多加一个变量来辅助，算是比较难的了。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击这里查看详情