动态规划

很神奇的一个做法。执行速度极快，超越了94%的用户。未完全理解，我先去搞懂84题再回来看 = =。

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

        int leftMax[matrix[0].size()];
        fill(leftMax, leftMax + matrix[0].size(), -1);

        int rightMin[matrix[0].size()];
        fill(rightMin, rightMin + matrix[0].size(), matrix[0].size());

        int maxS = 0, boundLeft = -1, boundRight = matrix[0].size();

        vector<int> heights(matrix[0].size());
        for (int i = 0; i < matrix.size(); i ++) {
            for (int j = 0; j < matrix[0].size(); j ++) {
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }

            boundLeft = -1;
            for (int j = 0; j < matrix[0].size(); j ++) {
                if (matrix[i][j] == '1') {
                    leftMax[j] = max(leftMax[j], boundLeft);
                } else {
                    leftMax[j] = -1;        //高度为0的矩形左边界为-1
                    boundLeft = j;
                }
            }

            boundRight = matrix[0].size();
            for (int j = matrix[0].size() - 1; j >= 0; j --) {
                if (matrix[i][j] == '1') {
                    rightMin[j] = min(rightMin[j], boundRight);
                } else {
                    rightMin[j] = matrix[0].size();
                    boundRight = j;
                }
            }

            for (int i = 0; i < matrix[0].size(); i ++) {
                maxS = max(maxS, heights[i] * (rightMin[i] - leftMax[i] - 1));
            }
        }
        return maxS;
    }
};