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.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

left[j]代表從之前的row到現在的row，連續在左側出現的1最左邊的位置。 right[j]代表從之前的row到現在連續出現在右側的1最右的位置。 height[j]代表從之前的row到現在的row，連續出現的1所形成的高度。 一開始把left初始化為0，right初始化為n。故意讓right array的值向右shift一單位，這樣最後算結果時不需要+1調整寬的值。

// Dynamic programming
int maximalRectangle(vector<vector<char>>& matrix) { // time: O(m * n); space: O(n)
    if (matrix.empty() || matrix[0].empty()) return 0;
    int res = 0, m = matrix.size(), n = matrix[0].size();
    vector<int> height(n, 0), left(n, 0), right(n, n);
    for (int i = 0; i < m; ++i) {
        int cur_left = 0, cur_right = n;
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == '1') 
                ++height[j];
            else 
                height[j] = 0;
        }
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == '1') 
                left[j] = max(left[j], cur_left);
            else {
                left[j] = 0; 
                cur_left = j + 1;
            }
        }
        for (int j = n - 1; j >= 0; --j) {
            if (matrix[i][j] == '1') 
                right[j] = min(right[j], cur_right);
            else {
                right[j] = n;
                cur_right = j;
            }
        }
        for (int j = 0; j < n; ++j) {
            res = max(res, (right[j] - left[j]) * height[j]);
        }
    }
    return res;
}