LeetCode开心刷题三十二天——85. Maximal Rectangle

超、凢脫俗 2021-10-23 07:57 240阅读 0赞

85. Maximal Rectangle

Hard

161653FavoriteShare

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
    
    IDEA:
    https://www.twblogs.net/a/5bc0fa7d2b717711c9241544/zh-cn
    The concept of monotone stack(单调栈) was introduced
    ONE IMPORTANT THING:
    dp[i][j] means the number of "1" in i rows before j columns.
    dp[1][2]代表在第一行中的第二列之前1的个数。

#include<stdio.h>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<set>
    #include<map>
    #include<algorithm>
    #include<climits>
    using namespace std;
    class Solution {
    public:
        int maximalRectangle(vector<vector<char>>& matrix) {
            //NULL judge very important
            int n1=matrix.size();
            if(n1==0) return 0;
            int n2=matrix[0].size();
            //dp[i][j] is the max number of 1 in columns j rows i
            //vector initializer special no need ==
            vector<vector<int>> dp(n1,vector<int>(n2));
            //initialization
            for(int i=0;i<n1;i++)
            {
                for(int j=0;j<n2;j++)
                {
                    //nested function need to pay attention whether finish all procedure such as this finish one easy to forget the latter ?:
                    dp[i][j]=(matrix[i][j]=='1')?(j==0?1:dp[i][j-1]+1):0;
                }
            }
    
            int ans=0;
    
            for(int i=0;i<n1;i++)
            {
                for(int j=0;j<n2;j++)
                {
                    int len = INT_MAX;
                    for(int k=i;k<n1;k++)
                    {
                        len=min(len,dp[k][j]);
                        if(len==0) break;
                        ans=max((k-i+1)*len,ans);
                    }
                }
            }
    
            return ans;
        }
    };
    
    int main()
    {
        vector<vector<char>> matrix=
        {
            {
          '1','0','1','0','0'},
            {
          '1','0','1','1','1'},
            {
          '1','1','1','1','1'},
            {
          '1','0','0','1','0'}
        };
        Solution s;
        int res=s.maximalRectangle(matrix);
        cout<<res<<endl;
        return 0;
    }

python version:
    1.python version why don't duplicate the C++'s thought,this
    method looks more complex.
    2.this version complex to understand but I add some print point help
    understand now paste method

class Solution(object):
        def maximalRectangle(self, matrix):
            """
            :type matrix: List[List[str]]
            :rtype: int
            """
            if not matrix or not matrix[0]: return 0
            M, N = len(matrix), len(matrix[0])
            height = [0] * N
            res = 0
            for row in matrix:
                for i in range(N):
                    if row[i] == '0':
                        height[i] = 0
                    else:
                        height[i] += 1
                    print("height1")
                    print(height)
                res = max(res, self.maxRectangleArea(height))
            return res
    
        def maxRectangleArea(self, height):
            if not height: return 0
            print("height")
            print(height)
            res = 0
            stack = list()
            print("stack0")
            print(stack)
            height.append(0)
            print("height2")
            print(height)
            for i in range(len(height)):
                cur = height[i]
                while stack and cur < height[stack[-1]]:
                    print("stack")
                    print(stack)
                    w = height[stack.pop()]
                    h = i if not stack else i - stack[-1] - 1
                    res = max(res, w * h)
                stack.append(i)
            return res
    
    solu = Solution()
    matirx=[
      ["1","0","1","0","0"],
      ["1","0","1","1","1"],
      ["1","1","1","1","1"],
      ["1","0","0","1","0"]
    ]
    print(solu.maximalRectangle(matirx))

转载于:https://www.cnblogs.com/Marigolci/p/11337427.html