欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode

程序员文章站 2022-07-06 19:55:39
...

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

class Solution {
public:
    int maximalRectangle(vector<vector<char>> &matrix) {
        if (matrix.size() == 0)
            return 0;
        int n = matrix.size(), m = matrix[0].size(), sum = 0;
        vector<int> height(m, 0), right(m, m), left(m, 0);
        for (int i = 0; i < n; i++) {
            int cur_left = 0, cur_right = m;
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1')
                    height[j]++;
                else
                    height[j] = 0;
            }
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1') {
                    left[j] = max(left[j], cur_left);
                } else {
                    left[j] = 0, cur_left = j + 1;
                }
            }
            for (int j = m - 1; j >= 0; --j) {
                if (matrix[i][j] == '1') {
                    right[j] = min(right[j], cur_right);
                } else {
                    right[j] = m, cur_right = j;
                }
            }
            for (int j = 0; j < m; j++) {
                sum = max(sum, (right[j] - left[j]) * height[j]);
            }
        }
        return sum;
    }
};