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.

For example, given the following matrix:

  1 0 1 0 0
  1 0 1 1 1
  1 1 1 1 1
  1 0 0 1 0

Return 6.

先按动态规划求出每一层能够达到的高度height，计算从第0层到这一层能够达到的最大矩形面积。
有了每一层的高度，只需要求出这个高度能够向左向右的距离l,此时l*h就是矩形的面积，这就转换成了求Largest Rectangle in Histogram

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

        int maxArea = 0;
        vector<int> height(matrix[0].size(), 0);
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                height[j] = matrix[i][j]=='0' ? 0 : (height[j] + 1);
            }
            maxArea = max(maxRect(height), maxArea);
        }
        return maxArea;
    }
private:
    int maxRect(vector<int> &h){
        if(h.size() == 0)
            return 0;
        int res = 0;
        vector<int> L(h.size(), 0);
        vector<int> R(h.size(), 0);
        vector<int> st(h.size(), 0);

        //利用单调栈计算height[i]向左能到达的索引处(这些索引处的高度均高于height[i])
        int t = 0;
        for(int i = 0; i < h.size(); i++){
            while(t > 0 && h[ st[t - 1] ] >= h[i]) 
                t--;
            L[i] = t==0? 0 :(st[t - 1] + 1);
            st[t++] = i;
        }

         //利用单调栈计算height[i]向右能到达的索引处(这些索引处的高度均高于height[i])
        t = 0;
        for(int i = h.size() - 1; i >= 0; i--){
            while(t > 0 && h[ st[t - 1] ] >= h[i]) 
                t--;
            R[i] = t == 0? h.size() : st[t - 1];
            st[t++] = i;
        }

        for(int i = 0; i < h.size(); i++)
            res = max(res, h[i] *(R[i] - L[i]));

        return res;
    }
};