1.题目描述:点击打开链接
2.解题思路:本题利用扫描法解决:从上向下扫描每一行,如果我们把每个格子向上延伸的连续空格看做一条悬线,并用up(i,j),left(i,j),right(i,j)表示格子(i,j)的悬线长度以及该悬线向左,向右能够运动的“运动极限”,即最远能够走到哪一列。这样,每个格子(i,j)对应着一个以第i行为下边界,高度为up(i,j),宽度为right(i,j)-left(i,j)的矩形,那么这些矩形中的面积最大值就是题目所求。因此,关键是如何快速的求出这三个数值。
当格子(i,j)不是空格时,3个数组的值均为0,否则up(i,j)=up(i-1,j)+1。同样可......
阅读全文