題目描述：

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

Example:

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 直方圖中最大的矩形一樣求解哈肖。主要思路是腾仅，每一行都可以看作是求解一個直方圖中的最大矩形蛔添。因此趾唱，只需要將每一層當(dāng)作直方圖的底，并向上構(gòu)造直方圖即可站欺。

直方圖的高可以用dp得到：

1. 若matrix[i][col] == 1, 則height[i] = height[i-1]+1
2. 若matrix[i][col] == 0, 則height[i] = 0

方法一：

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

第二種種方法的思路比較巧：
height 數(shù)組和上面一樣姨夹，
left[j]表示：包含第j列的連續(xù)都是1的左邊界的位置（若height[j]=0纤垂，則 left[j]=0）
right[j]表示：包含第j列的連續(xù)都是1的右邊界的位置再加1（加1是為了計算長度方便，直接減去左邊界位置就是長度）

那么對于任意一行的第j列磷账，矩形為 (right[j] - left[j]) * height[j]峭沦，我們舉個例子來說明，比如給定矩陣為：

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

第0行：

h: 1 1 0 0 1
l: 0 0 0 0 4
r: 2 2 5 5 5 

第1行：

h: 0 2 0 0 2
l: 0 1 0 0 4
r: 5 2 5 5 5 

第2行：

h: 0 0 1 1 3
l: 0 0 2 2 4
r: 5 5 5 5 5

第3行：

h: 0 0 2 2 4
l: 0 0 2 2 4
r: 5 5 5 5 5

第4行：

h: 0 0 0 0 5
l: 0 0 0 0 4
r: 5 5 5 5 5 

方法二：

    int maximalRectangle(vector<vector<char>>& matrix) {
        int row = matrix.size();
        if(row <= 0) return 0;
        int col = matrix[0].size();
        
        vector<int> left(col),right(col),height(col);
        int res = 0;
        
        for(int i = 0; i < col; i++){
            left[i] = 0;
            right[i] = col;
            height[i] = 0;
        }
        
        for(int i = 0; i < row; i++){
            int cur_left = 0, cur_right = col;
            
            //update height
            for(int j = 0; j < col; j++){
                if(matrix[i][j] == '1') height[j] += 1;
                else height[j] = 0;
            }
            
            //update left
            for(int j = 0; j < col; j++){
                if(matrix[i][j] == '1') {
                    left[j] = max(left[j],cur_left);
                }
                else {
                    left[j] = 0;
                    cur_left = j+1;
                }
            }
            
            //update right
            for(int j = col-1; j >= 0; j--){
                if(matrix[i][j] == '1') {
                    right[j] = min(right[j],cur_right);
                }
                else {
                    right[j] = col;
                    cur_right = j;
                }
            }
            
            //update res
            for(int j = 0; j < col; j++){
                res = max(res,(right[j]-left[j])*height[j]);
            }
        }
        
        return res;
    }