最大矩形

绝地灬酷狼 2023-02-11 15:30 174阅读 0赞

## 一、前言 ##

问题来源LeetCode 85，难度：困难

问题链接：[https://leetcode-cn.com/problems/maximal-rectangle/][https_leetcode-cn.com_problems_maximal-rectangle]

## 二、题目 ##

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

示例：

输入:
    [
      ["1","0","1","0","0"],
      ["1","0","1","1","1"],
      ["1","1","1","1","1"],
      ["1","0","0","1","0"]
    ]
    输出: 6

##  ##

## 三、思路 ##

**三种解法**

### 3.1 方法一 暴力解法 ###

一个坐标，我们约定在这个坐标右上方查找，找出包含这个坐标的最大矩形。所有坐标对于最大矩形即为所求。看下图分析，我们一坐标（1，1）为例：

![20200524112118737.png][]

1.第一列最大面积是3

![2020052411220838.png][]

2.包含第二列最大面积是4

![20200524112211735.png][]

3.包含第三列最大面积是3

![20200524112221235.png][]

坐标(1,1) 最大面积为4。找出所有坐标最大面积中最大值即为所求。

**复杂度分析**

*  时间复杂度：O(n2m2)。
 *  空间复杂度：O(1) 。不需要额外的空间。

### 3.2 方法二：对方法一优化 ###

方法一中求一个坐标最大面积，进行了横纵坐标遍历，在这个坐标上层也进行了一次横纵坐标遍历，我们可以在第一次横纵坐标遍历的时候，找出每一行到有几个连续的1，看图理解：

![2020052411233087.png][]

上图为坐标图，下图为横向连续为1的坐标即宽度。如果坐标点获得是从左往右，从下往上，则坐标点最大面积搜索需要与获得坐标点方向相反——向下搜索。以坐标（2，2）为例：

![20200524112441665.png][]

1.当前这一行最大面积为：2 = 2\*1

2.包含下一行最大面积为：4 = 2\*2

有方法一中两个方法搜索，变为一个方法搜索（向下）

**复杂度分析**

*  时间复杂度：O(n2m)。
 *  空间复杂度：O(nm) 。需要数组记录点的宽度。

### 3.3 方法三：栈实现 ###

方法二中，我们只计算以当前坐标为中心，向下搜索。我们继续观察一下这个图：

![20200524112515386.png][]

是不是可以找出这一列中包含的最大的面积，这样我们又可以省去一次遍历。参考《柱状图中最大的矩形多种解法》

《柱状图中最大的矩形多种解法》[https://blog.csdn.net/nie2314550441/article/details/106305399][https_blog.csdn.net_nie2314550441_article_details_106305399]

**复杂度分析**

*  时间复杂度：O(nm)。
 *  空间复杂度：O(n) 。需要数组记录点的宽度。

## 四、编码实现 ##

//==========================================================================
    /**
    * @file : MaximalRectangle.h
    * @title: 最大矩形
    * @purpose : 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
    *
    * 示例:
    * 输入:
    * [
    *   ["1","0","1","0","0"],
    *   ["1","0","1","1","1"],
    *   ["1","1","1","1","1"],
    *   ["1","0","0","1","0"]
    * ]
    * 输出: 6
    *
    * 来源：力扣（LeetCode）
    * 难度：困难
    * 链接：https://leetcode-cn.com/problems/maximal-rectangle
    *
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <vector>
    #include <stack>
    #include <algorithm>
    using namespace std;
    
    #define NAMESPACE_MAXIMALRECTANGLE namespace NAME_MAXIMALRECTANGLE {
    #define NAMESPACE_MAXIMALRECTANGLEEND }
    NAMESPACE_MAXIMALRECTANGLE
    
    // 方法一：动态规划
    // 复杂度分析
    // 时间复杂度：O(n2m2)。
    // 空间复杂度：O(1) 。不需要额外的空间。
    class Solution_1 
    {
    public:
        int maximalRectangle(vector<vector<char>>& matrix) 
        {
            // 参数判断 start
            if (matrix.empty())
            {
                return 0;
            }
    
            int h = matrix.size();
            int w = matrix[0].size();
            for (int i = 0; i < h; ++i)
            {
                if (w != matrix[i].size())
                {
                    return 0;
                }
            }
            // 参数判断 end
    
            int maxRectangle = 0;
            for (int i = 0; i < h; ++i)
            {
                for (int j = 0; j < w; ++j)
                {
                    if (matrix[i][j] == '1')
                    {
                        int num = maximalRectangle(matrix, w, h, j, i);
                        maxRectangle = num > maxRectangle ? num : maxRectangle;
                    }
                }
            }
    
            return maxRectangle;
        }
    
    private:
        // 右上方向搜索
        int maximalRectangle(vector<vector<char>>& matrix, int w, int h, int wi, int hi)
        {
            if (wi < 0 || wi >= w || hi < 0 || hi > h)
            {
                return 0;
            }
    
            if (matrix[hi][wi] == 0)
            {
                return 0;
            }
    
            int maxRectangle = 1;
            int maxWide = 0;
            int tempw = w;
            for (int i = hi; i < h; ++i)
            {
                maxWide = 0;
                for (int j = wi; j < tempw; ++j)
                {
                    if (matrix[i][j] != '1')
                    {
                        tempw = j;
                        break;
                    }
                    ++maxWide;
                }
    
                if ((i - hi + 1) * maxWide > maxRectangle)
                {
                    maxRectangle = (i - hi + 1) * maxWide;
                }
    
                if (maxWide == 0)
                {
                    break;
                }
            }
    
            return maxRectangle;
        }
    };
    
    // 方法二：动态规划
    // 复杂度分析
    // 时间复杂度：O(n2m)。
    // 空间复杂度：O(n*m) 。需要数组记录点的宽度。
    class Solution_2
    {
    public:
        int maximalRectangle(vector<vector<char>>& matrix)
        {
            // 参数判断 start
            if (matrix.empty())
            {
                return 0;
            }
    
            int h = matrix.size();
            int w = matrix[0].size();
            for (int i = 0; i < h; ++i)
            {
                if (w != matrix[i].size())
                {
                    return 0;
                }
            }
            // 参数判断 end
    
            vector<vector<int>> dp;
            dp.resize(w);
            for (int i = 0; i < w; ++i)
            {
                dp[i].resize(h);
            }
            vector<int> tp;
            tp.resize(h);
            int maxRectangle = 0;
            for (int i = 0; i < h; ++i)
            {
                for (int j = 0; j < w; ++j)
                {
                    if (matrix[i][j] == '1')
                    {
                        dp[j][i] = j == 0 ? 1 : dp[j-1][i] + 1;
                        int num = maximalRectangle(dp[j], i);
                        
                        maxRectangle = num > maxRectangle ? num : maxRectangle;
                    }
                    else
                    {
                        dp[j][i] = 0;
                    }
                }
            }
    
            return maxRectangle;
        }
    
    private:
        // 左下方向搜索
        int maximalRectangle(vector<int> dp, int index)
        {
            if (index < 0 || index >= dp.size())
            {
                return 0;
            }
    
            if (dp[index] == 0)
            {
                return 0;
            }
    
            int maxRectangle = dp[index];
            int minWide = dp[index];
            --index;
            for (int i = 2; index >= 0; ++i, --index)
            {
                if (dp[index] < 1)
                {
                    break;
                }
                else
                {
                    minWide = min(minWide, dp[index]);
                    maxRectangle = max(maxRectangle, minWide * i);
                }
            }
    
            return maxRectangle;
        }
    };
    
    // 方法三：栈
    // 复杂度分析
    // 时间复杂度：O(nm)。
    // 空间复杂度：O(n) 。需要数组记录点的宽度。
    class Solution_3
    {
    public:
        // 横向计数
        int maximalRectangle(vector<vector<char>>& matrix)
        {
            // 参数判断 start
            if (matrix.empty())
            {
                return 0;
            }
    
            int h = matrix.size();
            int w = matrix[0].size();
            for (int i = 0; i < h; ++i)
            {
                if (w != matrix[i].size())
                {
                    return 0;
                }
            }
            // 参数判断 end
    
            vector<int> dp(h,0);
            int maxRectangle = 0;
            for (int j = 0; j < w; ++j)
            {
                for (int i = 0; i < h; ++i)
                {
                    dp[i] = matrix[i][j] == '1' ? dp[i] + 1 : 0;
                    maxRectangle = max(maxRectangle, maximalRectangle(dp));
                }
            }
    
            return maxRectangle;
        }
    
        // 纵向计算 和maximalRectangle方法类似
        int maximalRectangleEX(vector<vector<char>>& matrix)
        {
            if (matrix.empty())
            {
                return 0;
            }
    
            int h = matrix.size();
            int w = matrix[0].size();
            for (int i = 0; i < h; ++i)
            {
                if (w != matrix[i].size())
                {
                    return 0;
                }
            }
    
            vector<int> dp(w, 0);
            int maxRectangle = 0;
            for (int i = 0; i < matrix.size(); ++i)
            {
                for (int j = 0; j < matrix[0].size(); ++j)
                {
                    dp[j] = (matrix[i][j] == '1') ? dp[j] + 1 : 0;
                }
                maxRectangle = max(maxRectangle, maximalRectangle(dp));
            }
    
            return maxRectangle;
        }
    
    private:
        int maximalRectangle(vector<int>& heights)
        {
            stack<int> st;
            heights.push_back(0);//结尾虚拟柱子高度0
            int size = heights.size();
            int res = 0;
            for (int i = 0; i < size; ++i)
            {
                while (!st.empty() && heights[st.top()] >= heights[i])
                {
                    int val = st.top();
                    st.pop();
                    res = max(res, heights[val] * (st.empty() ? i : (i - st.top() - 1)));//宽度不包含当前元素
                }
                st.push(i);
            }
            return res;
        }
    };
    
    
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, vector<vector<char>> & matrix, int expect)
    {
        Solution_1 s1;
        Solution_2 s2;
        Solution_3 s3;
    
    
        int result1 = s1.maximalRectangle(matrix);
        int result2 = s2.maximalRectangle(matrix);
        int result3 = s3.maximalRectangle(matrix);
    
    	if (result1 == expect && result2 == expect && result3 == expect)
    	{
    		cout << testName << ", solution passed." << endl;
    	}
    	else
    	{
    		cout << testName << ", solution failed. result1: " << result1 << ", result2: " << result2 << ", result3: " << result3 << endl;
    	}
    }
    
    void Test1()
    {
        vector<vector<char>> matrix{ {'1'} };
    	int expect = 1;
    
    	test("Test1()", matrix, expect);
    }
    
    void Test2()
    {
        vector<vector<char>> matrix{ {'1','1','1','1','1','1'} };
    	int expect = 6;
    
    	test("Test2()", matrix, expect);
    }
    
    void Test3()
    {
        vector<vector<char>> matrix{ {'1','0','1','1','1','0'} };
    	int expect = 3;
    
    	test("Test3()", matrix, expect);
    }
    
    void Test4()
    {
        vector<vector<char>> matrix{ {'1','1','1','1','1','1'} };
    	int expect = 6;
    
    	test("Test4()", matrix, expect);
    }
    
    void Test5()
    {
        vector<vector<char>> matrix{ {'1','0','1','1','1','0'} };
    	int expect = 3;
    
    	test("Test5()", matrix, expect);
    }
    
    void Test6()
    {
        vector<vector<char>> matrix
        { 
            {'1','0','1','0','0'}, 
            {'1','0','1','1','1'},
            {'1','1','1','1','1'},
            {'1','0','0','1','0'},
        };
    	int expect = 6;
    
    	test("Test6()", matrix, expect);
    }
    
    void Test7()
    {
        vector<vector<char>> matrix
        {
            {'1','1','1','1','1'},
            {'1','1','1','1','1'},
            {'1','1','1','1','1'},
            {'1','1','0','1','1'},
            {'1','1','1','1','1'},
            {'1','1','1','1','1'},
    
        };
    	int expect = 15;
    
    	test("Test7()", matrix, expect);
    }
    
    void Test8()
    {
        vector<vector<char>> matrix
        {
            {'1','0','0','1','1'},
            {'1','1','1','0','1'},
            {'0','1','1','1','1'},
            {'1','1','0','1','1'},
            {'1','1','1','1','1'},
            {'1','1','1','1','1'},
    
        };
    	int expect = 10;
    
    	test("Test8()", matrix, expect);
    }
    
    void Test9()
    {
        vector<vector<char>> matrix
        {
            {'1','1','1','1','1'},
            {'1','1','1','1','1'},
            {'1','1','1','1','1'},
            {'1','1','1','1','1'},
            {'1','1','1','1','1'},
            {'1','1','1','1','1'},
    
        };
    	int expect = 30;
    
    	test("Test9()", matrix, expect);
    }
    
    NAMESPACE_MAXIMALRECTANGLEEND
    // 测试 用例 END
    //
    
    
    void MaximalRectangle_Test()
    {
    	NAME_MAXIMALRECTANGLE::Test1();
    	NAME_MAXIMALRECTANGLE::Test2();
    	NAME_MAXIMALRECTANGLE::Test3();
    	NAME_MAXIMALRECTANGLE::Test4();
    	NAME_MAXIMALRECTANGLE::Test5();
    	NAME_MAXIMALRECTANGLE::Test6();
    	NAME_MAXIMALRECTANGLE::Test7();
    	NAME_MAXIMALRECTANGLE::Test8();
    	NAME_MAXIMALRECTANGLE::Test9();
    }

**执行结果：**

![20200524113010312.png][]

[https_leetcode-cn.com_problems_maximal-rectangle]: https://leetcode-cn.com/problems/maximal-rectangle/
[20200524112118737.png]: https://img-blog.csdnimg.cn/20200524112118737.png
[2020052411220838.png]: https://img-blog.csdnimg.cn/2020052411220838.png
[20200524112211735.png]: https://img-blog.csdnimg.cn/20200524112211735.png
[20200524112221235.png]: https://img-blog.csdnimg.cn/20200524112221235.png
[2020052411233087.png]: https://img-blog.csdnimg.cn/2020052411233087.png
[20200524112441665.png]: https://img-blog.csdnimg.cn/20200524112441665.png
[20200524112515386.png]: https://img-blog.csdnimg.cn/20200524112515386.png
[https_blog.csdn.net_nie2314550441_article_details_106305399]: https://blog.csdn.net/nie2314550441/article/details/106305399
[20200524113010312.png]: https://img-blog.csdnimg.cn/20200524113010312.png