Force deduction 85 question maximum rectangle

Power button 85 Question maximum rectangle

Title Description

Given a contains only 0 and 1 、 The size is rows x cols Two dimensional binary matrix , Find out that only 1 The largest rectangle of , And return its area .

I/o sample

 Input ：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 Output ：6
 explain ： The largest rectangle is shown above .

 Input ：matrix = []
 Output ：0

 Input ：matrix = [["0"]]
 Output ：0

 Input ：matrix = [["1"]]
 Output ：1

Solution one uses violent solution

   int maximalRectangle2(vector<vector<char>>&matrix)
    {
    
        int rlength=matrix.size();
        int clength=matrix[0].size();
        if(rlength==0)
        {
    
            return 0;
        }

        vector<vector<int>>width(rlength,vector<int>(clength));
        int maxArea=0;

        // Go through every line 
        for(int row=0;row<rlength;row++)
        {
    
            for(int col=0;col<clength;col++)
            {
    
                if(matrix[row][col]=='1')
                {
    
                    // The current value saves the current row 1 Value 
                    if(col==0)
                    {
    
                        width[row][col]=1;
                    }
                    else
                    {
    
                        width[row][col]=width[row][col-1]+1;
                    }
                }
                else{
    
                    width[row][col]=0;
                }

                // Record the minimum number of all rows 
                // Take the minimum value of the current column value as the width 
                int minWidth=width[row][col];
                for(int upRow=row;upRow>=0;upRow--)
                {
    
                    int height=row-upRow+1;
                    minWidth=min(minWidth,width[upRow][col]);
                    maxArea=max(maxArea,height*minWidth);
                }
            }
        }
            return maxArea;

    }

solution 2, Solve with stack

/ The idea of finding the maximum area in combination with the previous question 
    int maximalRectangle(vector<vector<char>>&matrix)
    {
    
        int rlength=matrix.size();
        int clength=matrix[0].size();

        vector<vector<int>>res(rlength,vector<int>(clength));

        for(int i=0;i<rlength;i++)
        {
    
            for(int j=0;j<clength;j++)
            {
    
                if(matrix[i][j]=='1')
                {
    
                    res[i][j]=1;
                }
                else{
    
                    res[i][j]=0;
                }
            }
        }
        for(int i=0;i<rlength-1;i++)
        {
    
            for(int j=0;j<clength;j++)
            {
    
                if(res[i+1][j])
                {
    
                    res[i+1][j]=res[i+1][j]+res[i][j];
                }
            }
        }

        int maxArea=0;

        for(int i=0;i<rlength;i++)
        {
    
            int temp=largestRectangleArea(res[i]);
            maxArea=max(temp,maxArea);
        }

        return maxArea;

    }

    int largestRectangleArea(vector<int>&height)
    {
    
        int length=height.size();
        if(length==0)
        {
    
            return 0;
        }
        else if(length==1)
        {
    
            return height[0];
        }

        // Create an array and save the sentry 
       vector<int>tempList(length+2);
        for(int i=0;i<length;i++)
        {
    
            tempList[i+1]=height[i];
        }
        tempList[0]=0;
        tempList[length+1]=0;
        int maxArea=0;

        length+=2;
        height=tempList;

        // Build stack , Put the sentry in the stack first 
        stack<int>stk;
        stk.push(0);
        for(int i=1;i<length;i++)
        {
    
            while(height[stk.top()]>height[i])
            {
    
                int high=height[stk.top()];
                stk.pop();
                int width=i-stk.top()-1;
                maxArea=max(maxArea,high*width);
            }
            stk.push(i);
        }
        return maxArea;
    }