LeetCode 85. Maximal Rectangle [Hard] [C++] 解題筆記

這題給定一個 2D array ，裡面只包含 "1" 或 "0" ，要我們求由 "1" 組成的最大矩形面積。

EX:

      [

      ["1","0","1","0","0"],
      ["1","0","1","1","1"],
      ["1","1","1","1","1"],
      ["1","0","0","1","0"]
   ]

    Ans: 6

想法:

        這道題主要有兩種作法，第一種是將它視為 84. Largest Rectangle in Histogram 的延伸，可以先去做 84 題再來做這題。我們可以將每一列是為一個獨立的 Histogram 圖來分別計算其中最大的矩形面積，之後再找出每一列形成的 Histogram 圖的最大矩形面積之間的最大者，其中 array 中的值代表每個 bar 的高度，而若該行正上方也是 1 則高度累加，若該行是 0 則表示高度為 0。

之後只要分別照著 84. 的方法就可以求出各個 row 分別的最大矩形面積拉，如下圖，可以發現答案就會是第三列的 Histogram 圖所形成的最大矩形面積 6 !。

first row:     

          1  0  1  0   0

             _      _  

          |_|__|_|____

second row:

           2  0  2  1  1

                   _      _

          |  |    |  | _  _

          |_|__|_||_||_|

third row:

          3  1  3  2 2

           _      _

         |  |    |_| _  _

         |  | _ |_||_||_|    

         |_||_||_||_||_|

fourth row:

          4  0 0  3  0

           _

         |  |         _

         |  |        |  | 

         |  |        |  | 

         |_|____|_| __ 

                   

第二種方法是使用 DP ，有點累了，先貼程式碼，之後再來總結。

完整程式碼:

解法一 (Monotonic stack):

class Solution {

public:

    int largestRectangleArea(vector<int>& heights) {

        vector<int> stack;

        heights.emplace_back(0);

        int i = 0;

        int max_area = 0;

        while (i < heights.size()) {

            if (stack.empty() || heights[i] >= heights[stack.back()]) {

                stack.emplace_back(i++);

            }

            else {

                int h = heights[stack.back()];

                stack.pop_back();

                int w = (stack.empty())? i : i - stack.back() - 1;

                max_area = max(max_area, w*h);

            }

        }

        return max_area;

    }

    int maximalRectangle(vector<vector<char>>& matrix) {

        if (matrix.empty() || matrix[0].empty()) { return 0; }

        vector<int> heights(matrix[0].size());

        int max_rect_area = 0;

        for (int i = 0; i < matrix.size(); i++) {

            for (int j = 0; j < matrix[0].size(); j++) {

                if (matrix[i][j] == '0') {

                    heights[j] = 0;

                }

                else {

                    heights[j] += 1;

                }

            }

            max_rect_area = max(max_rect_area, largestRectangleArea(heights));

        }

        

        return max_rect_area;

    }

};

解法二 (DP):

class Solution {

public:

    int maximalRectangle(vector<vector<char>>& matrix) {

        if (matrix.empty()) { return 0; }

        

        // dp[i][j] represent the maximum length from 0~j in row i

        vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size()));

        

        for (int i = 0; i < matrix.size(); i++) {

            for (int j = 0; j < matrix[i].size(); j++) {

                if (j == 0) {

                    dp[i][j] = (matrix[i][j] == '0')? 0 : 1;

                }

                else {

                    dp[i][j] = (matrix[i][j] == '0')? 0 : dp[i][j-1] + 1;           

                }

            }

        }

        

        int area = 0;

        for (int i = 0; i < matrix.size(); i++) {

            for (int j = 0; j < matrix[i].size(); j++) {

                int len = INT_MAX;

                for (int k = i; k < matrix.size(); k++) {

                    len = min(len, dp[k][j]);

                    if (len == 0) { break; }

                    area = max(area, len * (k - i + 1));

                }

            }

        }

        

        return area;

    }

};