Maximal Rectangle

Published: 30 Aug 2014 Category: 技术

题目

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

思路

先解决子问题, 即 matrix[0:i] 中最大矩形,这可以看成以第 i 行为底边,由1组成柱体,求最大矩形面积,问题即转化成 Largest Rectangle in Histogram 问题。我们只需要维护一个 列表 H, H[i] 代表以当前行为底边,第 i 列的高度。