[LeetCode] Maximal Rectangle

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

?

在做?Largest Rectangle in Histogram的時候有人說可以用在這題，看了一下還真是，以每行為x軸，每列往上累計的連續的1當成高度，就可以完全使用一樣的方法了。

int largestArea(vector<int>height){
    stack<int> s;
    int maxArea = 0;
    int i = 0;
    height.push_back(0);
    int len = height.size();

    while (i < len){
        if (s.empty() || height[s.top()] < height[i]){
            s.push(i++);
        }else{
            int t = s.top();
            s.pop();
            maxArea = max(maxArea, height[t] * (s.empty()? i : (i-s.top()-1)));
        }
    }
    return maxArea;
}

int maximalRectangle(vector<vector<char>> &matrix){
    vector<int> height;
    int maxRect=0;
    for (int row=0; row<matrix.size(); row++){
        for (int col=0; col<matrix[row].size(); col++){
            if (matrix[row][col] == '0'){
                height.push_back(0);
            }
            else{
                int c=0;
                for (int i=row; i>-1; i--){
                    if (matrix[i][col] != '0'){
                        c++;
                    }else {
                        break;
                    }
                }
                height.push_back(c);
            }
        }
        
        for (int i=0;i<height.size(); i++){
            cout << height[i] << " ";
        }
        cout << endl;
        
        maxRect = max(maxRect, largestArea(height));
        height.clear();
    }
    return maxRect;
}


int maximalRectangle2(vector<vector<char>> &matrix){
    int maxRect = 0;
    if (matrix.size() < 1) return 0;
    vector<int>height(matrix[0].size(), 0);
    for (int i=0; i<matrix.size(); i++){
        for (int j=0; j<matrix[i].size(); j++){
            if (matrix[i][j] == '1'){
                height[j] += 1;
            }else{
                height[j] = 0;
            }
        }
        maxRect = max(maxRect, largestArea(height));
    }
    return maxRect;
}

第一個maximalRectangle函數我用了很蠢的遍歷方法來獲得每行的height，這樣活生生的把原本O(n^2)搞成了O(n^3)。。。 最后看了別人博客，說height是可以通過前一行的值算出了的(有點類似DP的思想...如果這也算的話)，豁然開朗，才寫出了

maximalRectangle2這個真正的O(n^2)方法。