LeetCode 85. Maximal Rectangle题目解析-wowAC

Description

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.



题目复述

给定一个2维数组,只包含'0','1',最大的'1'围成的矩形并返回面积

题目解析

这道题是LeetCode 84. Largest Rectangle in Histogram的拓展版,在84题里求的是静态的最大矩形,这里我们以每一行为底,从底到上面连续的1的个数为高,就把这道题转化成了84题,在求连续的1的个数的时候可以使用递推的方式,求第i行的连续的1的个数的时候,如果第i行为1,那就是i-1行的个数+1,如果为0,那第i行就是0.

class Solution {
public:
    //直接拷贝的84的代码
    int largestRectangleArea(vector<int>& heights) {
        vector<int> st; //栈 用于存储下标
        vector<int> L(heights.size());  //L[i]表示i左边距离i最近的heights小于heights[i]的位置
        vector<int> R(heights.size());  //R[i]表示i右边距离i最近的heights小于heights[i]的位置
        for(int i=0; i<heights.size(); i++) {
            while(!st.empty() && heights[st[st.size()-1]]>=heights[i])
                st.pop_back();
            if(st.empty()) L[i] = -1;
            else L[i] = st[st.size()-1];
            st.push_back(i);
        }
        st.clear();
        
        for(int i=heights.size()-1; i>=0; i--) {
            while(!st.empty() && heights[st[st.size()-1]]>=heights[i])
                st.pop_back();
            if(st.empty()) R[i] = heights.size();
            else R[i] = st[st.size()-1];
            st.push_back(i);
        }
        st.clear();
        
        int res = 0;
        for(int i=0; i<heights.size(); i++) {
            res = max(res, heights[i]*(R[i]-(L[i]+1)));
        }
        return res;
    }
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size()==0) return 0;  //空矩阵
        vector<int> heights(matrix[0].size());
        int res = 0;
        for(int i=0; i<matrix.size(); i++) {
            //求解第i行连续的1的个数
            for(int j=0; j<matrix[i].size(); j++)
                if(matrix[i][j] == '0') heights[j] = 0;
                else heights[j] += 1;
            res = max(res, largestRectangleArea(heights));
        }
        return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注