85 最大矩形

题目

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：

输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出：6
解释：最大矩形如上图所示。
示例 2：

输入：matrix = []
输出：0
示例 3：

输入：matrix = [[“0”]]
输出：0
示例 4：

输入：matrix = [[“1”]]
输出：1
示例 5：

输入：matrix = [[“0”,“0”]]
输出：0

• 法一：对矩阵的每一列，查找柱状图中的最大矩形

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m=matrix.size(),n=matrix[0].size();//记录矩阵的长和宽
        vector<int> height(n,0);//存储以当前行为下边界，每一列的高度(从当前行向上数连续1的个数)
        //当前行开始连续1的个数，实际上为上一行对应位置的数字加上当前行的判断。如果当前行对应位置为0，则为0；如果为1，则为上一行对应位置个数加1
        int result=0;
        for(int i=0;i<m;i++)
        {
        	//以每一行为坐标轴，计算当前当前行及以上位置，柱状图中的最大矩形面积
        	//for循环确定柱状图中每个位置的高度
            for(int j=0;j<n;j++)
            {
                if(matrix[i][j]=='1')
                {
                    height[j]++;
                }else height[j]=0;
            }
            //确定当前行及以上的最大矩形面积
            result = max(result, maxRectangle(height));
        }

        return result;
    }
	
	//确定当前行及以上的最大矩形面积
    int maxRectangle(const vector<int>& height)
    {
        stack<int> index;//栈，存储height数组的下标
        int result=0;//最大矩形面积
        int n=height.size();
        //遍历数组，计算以每一个数字为高时的最大矩形面积，在其中取最大值
        for(int i=0;i<n;i++)
        {	
        	//如果栈非空，且当前元素的高度小于栈顶元素高度，则栈顶元素找到了右边界，此时计算矩形高度
        	//栈顶元素的左边界就是栈中的倒数第二个元素
            while(!index.empty()&&height[i]<height[index.top()])
            {
                int he=height[index.top()];//记录当前矩形高度
                index.pop();//弹栈
                int len=i;//记录当前矩形宽
                if(!index.empty()) len=i-index.top()-1;
                result=max(result,he*len);
            }
            index.push(i);
        }
        //此时i已经遍历全部数组，栈中剩余元素单调递增，且右边界均为n。计算矩形面积，更新最大值
        while(!index.empty())
        {
            int he=height[index.top()];
            index.pop();
            if(index.empty()) result=max(result,he*n);
            else result=max(result,he*(n-index.top()-1));
        }
        return result;
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

• 时间复杂度O(mn)

• 空间复杂度O(n)

• 思路

  • 将求矩阵中的最大矩形面积，转化为，固定横轴求柱状图中的最大矩形面积
  • 求当前横轴对应的柱状图高度：如果当前行该位置的元素为0，则高度为0.如果当前行该位置的元素为1，则高度为上一行该位置高度加一
  • 求柱状图中最大矩形面积函数解析：https://blog.csdn.net/weixin_45781228/article/details/119894579

• 法一：代码优化，在height数组的首尾添加哨兵

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m=matrix.size(),n=matrix[0].size();
        vector<int> height(n,0);
        int result=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(matrix[i][j]=='1')
                {
                    height[j]++;
                }else height[j]=0;
            }
            result = max(result, maxRectangle(height));
        }

        return result;
    }
	//在height数组的首尾添加哨兵0，计算矩形长度时不用判断栈空
    int maxRectangle(const vector<int>& height)
    {
        stack<int> index;
        int result=0;
        vector<int> height2(height);
        height2.push_back(0);
        height2.insert(height2.begin(),0);
        int n=height2.size();
        index.push(0);
        for(int i=1;i<n;i++)
        {
            while(!index.empty()&&height2[i]<height2[index.top()])
            {
                int he=height2[index.top()];
                index.pop();
                int len=i-index.top()-1;
                result=max(result,he*len);
            }
            index.push(i);
        }
        return result;
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

• 法二：动态规划

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty()) return 0;//去除矩阵为空的情况
        int m=matrix.size(),n=matrix[0].size();
        //H[i]表示当前行i处矩形对应的高，L[i]表示当前左边离i处最近的字符0的下标，R[i]表示当前右边离i处最近的字符0的下标
        //为了避免边界问题导致出错，选择L数组中-1作为标志位，选择R数组中n作为标志位
        vector<int> H(n,0),L(n,-1),R(n,n);
        int result=0;//记录当前的最大矩形面积
		//每一层for循环记录当前行及以上的最大矩形面积
        for(int i=0;i<m;i++)
        {
            int left=-1,right=n;//left为当前已经访问过的字符中最右边0对应的下标，right为从右往左访问过的字符中最左边0对应的下标
            //填L数组和H数组，从左往右遍历当前行
            for(int j=0;j<n;j++)
            {
                if(matrix[i][j]=='1')//如果为1，当前位置矩形的高度为上一行高度加1，距离当前位置最近的0的下标为上一行当前位置最近的0和left，二者取较大值
                {
                    H[j]++;
                    L[j]=max(L[j],left);
                }else{//如果为0，更新left的值，当前位置的矩形高度为0，距离当前位置最近的0的下标置为标志位
                    left=j;
                    H[j]=0;L[j]=-1;
                }
            }
            //填R数组然后计算当前矩形的面积
            for(int j=n-1;j>=0;j--)
            {
                if(matrix[i][j] == '1')//如果当前数字为1，更新R数组，计算矩形面积
                {
                    R[j]=min(R[j],right);
                    result=max(result,H[j]*(R[j]-L[j]-1));
                }else{//如果为0，更新right和R数组对应位置为标志位
                    right=j;
                    R[j]=n;
                }
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

• 时间复杂度O(mn)
• 空间复杂度O(n)
• 思路
  • 动态规划。采用三个数组，H记录当前位置矩形的高，L记录当前位置矩形左边界，R记录当前位置矩形的右边界
  • 当前行的数据可以使用上一行的数据。当前行H的值，如果字符为1就是上一行对应位置的值加一。当前行L的值就是上一行对应位置L的值与left取较大者。当前行R的值就是上一行对应位置R的值与right取较小者
  • 详细查看代码注释