85. Maximal Rectangle

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

Input:
[
[“1”,“0”,“1”,“0”,“0”],
[“1”,“0”,“1”,“1”,“1”],
[“1”,“1”,“1”,“1”,“1”],
[“1”,“0”,“0”,“1”,“0”]
]
Output: 6

这道题目使用本是想使用动归但是苦于很难找到合适的对于子问题的划分。
介于Largest Rectangle in Histogram的启发式算法，应用于这道题目。
最终的时间复杂度为o(n*m)

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        if(n==0) return 0;
        if(n==1) return heights[0];
        int res = 0;
        heights.push_back(0);
        stack<int> s;
        for(int i=0;i<n+1;++i) {
            if(s.empty()||heights[i]>heights[s.top()])
                s.push(i);
            else {
                while(!s.empty()&&heights[i]<heights[s.top()]) {
                    int t = s.top();
                    s.pop();
                    int h = heights[t];
                    int w = 0;
                    if(!s.empty())
                        w = i - s.top() - 1;
                    else 
                        w = i - 0;
                    res = max(res,h*w);
                }
                s.push(i);
            }
        }
        return res;
    }
    
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size();
        if(!n) return 0;
        int m = matrix[0].size();
        if(!m) return 0;
        if(n==1&&m==1) return matrix[0][0]=='1';
        int res = 0;
        
        vector<int> dp(m,0);
        for(int i=0;i<n;++i) {
            for(int j=0;j<m;++j) {
                dp[j] = (matrix[i][j]=='1')?dp[j]+1:0;
            }
            res = max(res,largestRectangleArea(dp));
        }
        
        return res;
    }
};