[LeetCode]*85.Maximal Rectangle

题目

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

思路

对于上图的一个01矩阵。我们可以一行一行的分析，假设第三行，我们按列扫描，遇到0时，柱子断开，重新形成柱子，遇到1时柱子高度加一。这样的话，我们就可以把问题转换为[LeetCode]*84.Largest Rectangle in Histogram求解最大矩形面积。

代码

/*---------------------------------------
*   日期：2015-05-14
*   作者：SJF0115
*   题目: 85.Maximal Rectangle
*   网址：https://leetcode.com/problems/maximal-rectangle/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int row = matrix.size();
        if(row == 0){
            return 0;
        }//if
        int col = matrix[0].size();
        vector<vector<int> > height(row,vector<int>(col,0));
        // 计算每一行的高度
        int h;
        for(int j = 0;j < col;++j){
            h = 0;
            for(int i = 0;i < row;++i){
                if(matrix[i][j] == '1'){
                    ++h;
                }//if
                else{
                    h = 0;
                }//else
                height[i][j] = h;
            }//for
        }//for
        /*for(int i = 0;i < row;++i){
            for(int j = 0;j < col;++j){
                cout<<height[i][j]<<" ";
            }
            cout<<endl;
        }//for*/
        // 计算以第i行为底的矩形面积
        int maxArea = 0;
        for(int i = 0;i < row;++i){
            maxArea = max(maxArea,MaxRectangle(height[i]));
        }//for
        return maxArea;
    }
private:
    int MaxRectangle(vector<int> height){
        int size = height.size();
        if(size == 0){
            return 0;
        }//if
        int maxArea = 0;
        stack<int> indexStack;
        int top,width;
        for(int i = 0;i < size;++i){
            if(indexStack.empty() || height[i] >= height[indexStack.top()]){
                indexStack.push(i);
            }//if
            else{
                top = indexStack.top();
                indexStack.pop();
                width = indexStack.empty() ? i : (i - indexStack.top() - 1);
                maxArea = max(maxArea,height[top] * width);
                --i;
            }//else
        }//for
        while(!indexStack.empty()){
            top = indexStack.top();
            indexStack.pop();
            width = indexStack.empty() ? size : (size - indexStack.top() - 1);
            maxArea = max(maxArea,height[top] * width);
        }//while
        return maxArea;
    }
};

int main(){
    Solution s;
    vector<vector<char> > matrix = {
        {'0','1','0','1','1'},
        {'1','1','1','0','0'},
        {'1','1','1','1','0'},
        {'1','0','1','1','1'},
        {'0','1','0','0','0'}
    };
    cout<<s.maximalRectangle(matrix)<<endl;
    return 0;
}

运行时间

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>