85. Maximal Rectangle

Problem from leetcode 85. Maximal Rectangle

---

这道题在poj 1964 City Game和poj 3494 Largest Submatrix of All 1’s有原题。
这是一道典型的 dynamic programming 问题。我们既可以用 84. Largest Rectangle in Histogram相似的解法又可以用 53. Maximum Subarray的idea。在poj 1964 City Game的online judge中，O(n³)的算法是通不过的，不过这里可以通过。

---

1, idea from “Largest Rectangle in Histogram”

我们可以写一个两层的循环构造数字数组，然后用Largest Rectangle in Histogram的解法求最大的rectangle.

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int row = matrix.size();
        if(row == 0) return 0;
        int col = matrix[0].size();
        if(col == 0) return 0;
        
        int maximum = 0;
        vector<int> height(col, 0);

        for(int r = 0; r < row; r++)
        {
            for(int c = 0; c < col; c++) 
                if(matrix[r][c] == '1') 
                    ++height[c]; 
                else 
                    height[c] = 0; 
            int tmp = largestRectangleArea(height); 
            maximum = maximum>tmp?maximum:tmp;
        }
        return maximum;
    }
    //this function is extracted from problem "Largest Rectangle in Histogram"
    int largestRectangleArea(vector<int>& height) {
        height.push_back(0);
        int maximum = 0;
        int size = height.size();
        stack<int> barIndex;
        for(int i = 0; i < size; ++i) 
        { 
            if(barIndex.empty() || height[i] > height[barIndex.top()])
                barIndex.push(i);
            else
            {
                //we use height[index] as the right edge of found rectangle
                int index = barIndex.top(); barIndex.pop();
                int length = barIndex.size()==0?i:i-barIndex.top()-1;
                maximum = maximum<length*height[index]?length*height[index]:maximum;
                --i;
            }
        }
        return maximum;
    }
};

很明显上面的代码时间复杂度是O(n²).

---

2, idea from “Maximum Subarray”

用maximum subarray类似的idea的话时间复杂度是O(n³):

class Solution {
public:
    int maximalRectangle(vector<vector<char> >& matrix) {
        int row = matrix.size();
        if(row == 0) return 0;
        int col = matrix[0].size();
        if(col == 0) return 0;
        
        int maxi = 0;
        for(int startr = 0; startr < row; ++startr)
        {
            vector<int> arr(col, 0);
            for(int endr = startr; endr < row; ++endr)
            {
                for(int c = 0; c < col; ++c)
                    if(matrix[endr][c] == '0')
                        arr[c] = 0;
                    else
                        ++arr[c];
                maxi = max(maxi, maximumSubArray(arr));
            }
        }
        return maxi;
    }
    
private:
    int maximumSubArray(vector<int> &arr)
    {
        int size = arr.size();
        if(size == 0) return 0;
        int maxi = 0, pre = 0, count = 1;
        for(int i = 1; i < size; ++i)
            if(arr[i] != arr[pre])
            {
                maxi = max(maxi, count*arr[pre]);
                count = 1;
                pre = i;
            }
            else
                ++count;
        maxi = max(maxi, count*arr[pre]);
        return maxi;
    }
};