给一个二维数组,用0,1填充,找出包含1的矩形的最大面积.
开始想到的思路是,比较好的时间复杂度应该是n方,动态规划(似乎看到二维数组,首先就想到DP,估计跟最近做的几个二维DP的题目有关,还是得好好总结,建立方法论).即f[i][j]纪录以matrix[i][j]为右下顶点的矩形的最大面积.但是这样出现了一个问题,到f[i][j]的转移方程没法写,无法从f[i-1][j]/f[i][j-1]得到,思维还是存在漏洞.
正确思路:这个题目应该跟一维数组时,求最大能够容纳的水容量,或者是两根柱子组成的面积最大,连续整数的最大长度这些题一个类型,只是把数组从一维变成了二维.这样的话,按照原来两遍夹逼的思路.两个全局的数组L,R,对每一列都适用,即纪录当前行位置,第j列的最大允许的左边界以及右边界.两个局部的指针left,right,纪录当前行每个位置的左边界与右边界.并且通过left与right去更新L,R数组.
完整代码: