[LeetCode]Maximal Rectangle

这道题要用到Maximum Rectangle in Histogram的解法，本质上这一题每一层就是一个histogram，所以我们维护一个数组，从上向下扫每一层更新一下histogram的高度，然后再找maximum rectangle in histogram，最后返回最大的就可以。假设我们输入的char board[i][j]，f[j]代表当前层j位置直方的高度，DP方程是

• if board[i][j] == '0', f[j] = 0;
• else, f[j] = f[j] + 1;

假设输入数组有m列，n行，总的时间复杂度是O(m * n)，空间复杂度是O(n)，代码如下：

另外更General的解法也是用DP，对于每一个为1的点，我们要维护三个变量，也就是其左右边界left，right和高度height，我们可以在每一行每一行遍历的过程中更新这些值。假如我们是从上到下遍历的话：

• height[i]维护的是当前行第i个元素上面有多少个连续的1，包括自己
• left[i]维护的是当前元素所在的高度为height[i]的矩形的左边界
• right[i]维护的是当前元素所在的高度为height[i]的矩形的右边界

因此从第0行开始到当前行为止，对于每一个不同高度的矩形，在知道左右边界的情况下，我们可以算出面积最大值，那么遍历完所有行的话，在知道每一个高度对应的最大矩形的情况下，我们可以找出面积最大的矩形。我们用left[i]，right[i]和height[i]来表示当前行第i列的元素其所在的最大rectangle的最右边界和高度，那么我们有递归公式：

• 如果当前为1
• left[i] = max(left[i], currLeft)，currLeft为当前元素在当前行的连续的1的左边界
• right[i] = min(right[i], currRight, 同理
• height[i] = height[i] + 1
• 如果为0
• left[i] = 0，更新currLeft
• right[i] = n - 1，更新currRight
• height[i] = 0

我们不断更新rectangle的最大面积即可。每一行我们只需要左右各扫一次，时间按复杂度还是O(m * n)，空间复杂度O(n)，代码如下：