LeetCode: 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.

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        std::ios::sync_with_stdio(false);
        std::cin.tie(NULL);
        if (matrix.empty()) return 0;

        auto res = 0;
        for (auto i = 0; i < matrix.size(); ++i) {
            for (auto j = 0; j < matrix[0].size(); ++j) {
                if (matrix[i][j] == '1') {
                    calculate(i, j, res, matrix);
                }
            }
        }
        return res;
    }

    auto calculate(int i,int j,
                int& res,
                vector<vector<char>>& matrix) -> void {
        auto length = 1, height = 1;
        // 先寻找当前行最右边距离
        for (auto x = j; x < matrix[0].size(); ++x) {
            if (x != matrix[0].size() - 1 && matrix[i][x + 1] == '1') continue;
            // x是最后一个 或者 下一个不是1
            length = x - j + 1;
            res = max(length, res);
            break;
        }

        for (auto y = i + 1; y < matrix.size(); ++y) {
            if (matrix[y][j] == '1') {
                ++height;
                for (auto x = j; x < j+length; ++x) {
                    if (x != matrix[0].size() - 1 && matrix[y][x + 1] == '1' && x+1 != j+length) continue;

                    length = min(x - j + 1, length);
                    res = max(height * length, res);
                }
            }
            else {
                break;
            }
        }
    }
};

Runtime: 24 ms, faster than 74.02%
Memory Usage: 10.5 MB, less than 100.00%