這個題比剛才那個更難。如果沒做過上一個,這個簡直是無情。
先想一個笨笨的解法,怎樣確定一個矩形呢?找一個左上角,然後每行的看能延伸到什麼位置,注意隨著行數的增加,列數是只能變短,不能變長。想一下也知道這種方法的復雜度有多高,超時無疑。
如果剛好做了這個求柱形的題目,會不會收到啟發呢。將矩陣中的每一個1都看做是一個小的正方形,在每一列,連續的1就構成了一個柱體,求一連串這樣的柱體圍成的最大面積就是所有1構成的最大矩形,問題被完美轉化。雖然在我看來,這種轉化是非常不容易的,要不是這兩個題目相鄰,太難想到了。這給了我們很好的教訓,不同的形狀之間也許存在著某種聯系。
置於怎麼構造這樣的柱形就簡單的多了,每一行都需要計算,看當前行當前列是1還是0,是1的話在上一行對應列的基礎上長高1,是0的話直接就是0了。返回最大的面積。
class Solution { public: int largestArea(int *height, int length){ stacks; int i=0, res=0, tpres, tph; while(i > &matrix) { int m = matrix.size(); if(m == 0) return 0; int n = matrix[0].size(); int **h = new int*[m]; for(int i=0;i