程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode第一刷_Maximal Rectangle

leetcode第一刷_Maximal Rectangle

編輯:C++入門知識

這個題比剛才那個更難。如果沒做過上一個,這個簡直是無情。

先想一個笨笨的解法,怎樣確定一個矩形呢?找一個左上角,然後每行的看能延伸到什麼位置,注意隨著行數的增加,列數是只能變短,不能變長。想一下也知道這種方法的復雜度有多高,超時無疑。

如果剛好做了這個求柱形的題目,會不會收到啟發呢。將矩陣中的每一個1都看做是一個小的正方形,在每一列,連續的1就構成了一個柱體,求一連串這樣的柱體圍成的最大面積就是所有1構成的最大矩形,問題被完美轉化。雖然在我看來,這種轉化是非常不容易的,要不是這兩個題目相鄰,太難想到了。這給了我們很好的教訓,不同的形狀之間也許存在著某種聯系。

置於怎麼構造這樣的柱形就簡單的多了,每一行都需要計算,看當前行當前列是1還是0,是1的話在上一行對應列的基礎上長高1,是0的話直接就是0了。返回最大的面積。

class Solution {
public:
    int largestArea(int *height, int length){
        stack s;
        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



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved