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.
For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.
题目大意： 在给定 01 矩阵中，找出最大的只含有 1 的矩阵的面积。

解题思路

分别以每一行作为待求矩阵的底边，则该题可以转化为多个 LeetCode: 84. Largest Rectangle in Histogram 子问题。如，例子给的矩阵可以转化为高度为 [1, 0, 1, 0, 0], [2, 0, 2, 1, 1], [3, 1, 3, 2, 2], [4, 0, 0, 3, 0] 四个子问题。如图：

• 第一行：
  

• 第二行：
  

• 第三行：
  

• 第四行：
  

子问题的解法如上一篇题解 LeetCode: 84. Largest Rectangle in Histogram

AC 代码

class Solution {
private:
    // 84. Largest Rectangle in Histogram
    int largestRectangleinHistogramArea(vector<int>& heights)
    {
        // [startPos[i], endPos[i]]: 表示小于等于 heights[i] 的元素的包含 i 的最大区间
        vector<int> startPos(heights.size(), 0), endPos(heights.size(), heights.size());

        for(size_t i = 1; i < heights.size(); ++i)
        {
            int left = i-1;
            startPos[i] = i;
            while(left >= 0 && heights[i] <= heights[left])
            {
                startPos[i] = startPos[left];
                left = startPos[left] - 1;
            }
        }

        for(int i = heights.size()-1; i >= 0; --i)
        {
            int right = i + 1;
            endPos[i] = i;
            while(right < heights.size() && heights[i] <= heights[right])
            {
                endPos[i] = endPos[right];
                right = endPos[right] + 1;
            }
        }

        int ans = 0;
        for(size_t i = 0; i < heights.size(); ++i)
        {
            ans = max(ans, heights[i]*(endPos[i] - startPos[i] + 1));
        }

        return ans;
    }
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty()) return 0;

        int ans = 0;
        vector<int> heights(matrix[0].size(), 0);

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

            ans = max(ans, largestRectangleinHistogramArea(heights));
        }

        return ans;
    }
};