柱状图中最大的矩形多种解法

痛定思痛。 2023-02-11 12:28 10阅读 0赞

## 一、前言 ##

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

问题链接：[https://leetcode-cn.com/problems/largest-rectangle-in-histogram/][https_leetcode-cn.com_problems_largest-rectangle-in-histogram]

## 二、题目 ##

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

**示例：**

![20200523200938141.png][]

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 \[2,1,5,6,2,3\]。

![20200523201002383.png][]

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

**示例:**

输入: [2,1,5,6,2,3]
    输出: 10

## 三、思路 ##

**三种解法**

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

1.  从左往右遍历，每一个矩形
2.  对于当前遍历的矩形，它包含它在内的最大矩形是，向右和向左分别找到第一个高度小于它的矩形，它们围起来的矩形即为最大矩形。
3.  找到遍历中最大的矩形即为所求

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

上图输入为 : \[5,7,8,10,4,4,5,7\]

坐标0：高度5， 左边没有大于或等于的矩形，右边到坐标3，面积：20 = 5\*4

坐标1：高度7， 左边没有大于或等于的矩形，右边到坐标3，面积：21 = 7\*3

坐标2：高度8， 左边没有大于或等于的矩形，右边到坐标3，面积：16 = 8\*2

坐标3：高度10，左边没有大于或等于的矩形，右边没有， 面积：10 = 10\*1

坐标4：高度4， 左边到坐标1，右边到坐标7，面积：32 = 4\*8

坐标5：高度4， 和上一个坐标5高度相等，最大面积也相等，不用计算

坐标6：高度5， 左边没有，右边到坐标7，面积：10 = 5\*2

坐标7：高度7， 左边没有，右边没有，面积：7 = 7\*1

最大面积为：32

**复杂度分析**

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

### 3.2 方法二：分治法 ###

通过观察，可以发现，最大面积矩形存在于以下几种情况：

1.  确定了最矮柱子以后，矩形的宽尽可能往两边延伸。
2.  在最矮柱子左边的最大面积矩形（子问题）。
3.  在最矮柱子右边的最大面积矩形（子问题）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 2][]

上图输入为 : \[5,7,8,10,4,4,5,7\]

1.当前第一个最小高度为4（坐标4），最小高度最大矩形面积为 32 = 4\*8。

2.矩形左边（坐标0-3）最大面积：15。

3.矩形右边（坐标6-7）最大面积：10。（备注：坐标5和坐标4相邻且高度相等，最大面积已经计算）

**复杂度分析**

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

### 3.3 方法三：栈 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 3][]

方法一中是按照给定的矩形，向左右两边寻找至下一个小于它的高度。继续观察这个图发现当f(n) < f(n-1) 的时候，f(n)不再需要向右查找，只需要向左查找。那需要向左查找到什么时候为止呢？只需要保证左边为升序即可。以上图为例。

1. f(0) < f(1) < f(2) < f(3) , f(4) 不大于f(3)，往前寻找到小于f(4)为止，也就是当我们遍历到f(4) 时，已经可以确定 f(3)所包含的最大矩形面积：10 = 10\*1

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 4][]

2. 接着往前寻找，f(2) > f(4)，f(2)包含的最大矩形面积可以确定：16 = 8\*2

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 5][]

3. 接着往前寻找，f(1) > f(4)，f(1)包含的最大矩形面积可以确定：21 = 7\*3

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 6][]

4. 接着往前寻找，f(0) > f(4)，f(0)包含的最大矩形面积可以确定：20 = 5\*4

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 7][]

5. f(4) 是当前最小的高度，往前查找，f(5) 等于 f(4)，坐标5包含的最大矩形和坐标4包含的最大矩形，不用重复计算

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 8][]

6. f(6) > f(4)，f(7) > f(6) 继续往后搜索，已经到头了（可以在最后面添加高度为0的矩形）。往前搜索，

同理f(7)包含的最大矩形面积可以确定：7 = 7\*1

f(6)包含的最大矩形面积可以确定：10 = 5\*2

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 9][]

7. 现在只剩下 f(4)，剩下的最后一个即为高度最低的一个面积为 f(4) = 4\*8

**总结：**

分析完我们发现，从左往右遍历，当f(n) > f(n-1)需要放入队列里面；当f(n) <= f(n-1)的时候，f(n-1)最大面积可以确认，f(n-1)离开队列，继续判断队列首元素，直至小于f(n)为止。我们可以用栈维持这个队列。栈中元素为坐标值。

**复杂度分析**

*  时间复杂度：O(n)。
 *  空间复杂度：O(n) 。需要维持一个栈。

## 五、编码实现 ##

//==========================================================================
    /**
    * @file : 84_LargestRectangleArea.h
    * @title: 柱状图中最大的矩形
    * @purpose : 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，能够勾勒出来的矩形的最大面积。
    *
    * 示例:
    *
    * 输入:
    * 输入: [2,1,5,6,2,3]
    * 输出: 10
    *
    * 来源：力扣（LeetCode）
    * 难度：困难
    * 链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
    *
    */
    //==========================================================================
    #pragma once
    
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <stack>
    
    using namespace std;
    
    #define NAMESPACE_LARGESTRECTANGLEAREA namespace NAME_LARGESTRECTANGLEAREA {
    #define NAMESPACE_LARGESTRECTANGLEAREAEND }
    NAMESPACE_LARGESTRECTANGLEAREA
    
    // 解法一：暴力解决
    // 复杂度分析
    // 时间复杂度：O(n2)。
    // 空间复杂度：O(1) 。不需要额外的空间。
    //
    // 执行用时 : 1836 ms, 在所有 C++ 提交中击败了 5.00 % 的用户
    // 内存消耗 : 7.5 MB, 在所有 C++ 提交中击败了 100.00 % 的用户
    class Solution_1
    {
    public:
        int largestRectangleArea(vector<int>& heights)
        {
            int maxArea = 0;
            for (int i = 0; i < heights.size(); ++i)
            {
                if (i > 0 && heights[i] == heights[i - 1])
                {
                    // 如果和前面相等之前已经计算过
                    continue;  
                }
    
                int wide = 1;
    
                // 向前搜索
                for (int j = i + 1; j < heights.size() && heights[j] >= heights[i]; ++j, ++wide);
            
                // 向后搜索
                for (int j = i - 1; j >= 0 && heights[j] >= heights[i]; --j, ++wide);
     
                maxArea = max(heights[i] * wide, maxArea);
            }
    
            return maxArea;
        }
    };
    
    // 解法二：分治法
    // 复杂度分析
    // 时间复杂度：O(nlogn)。
    //空间复杂度：O(n) 。不需要额外的空间。
    //
    // 执行用时: 632 ms, 在所有 C++ 提交中击败了 8.53 %的用户
    // 内存消耗 : 14 MB, 在所有 C++ 提交中击败了 9.52 % 的用户
    class Solution_2 
    {
    public:
        int largestRectangleArea(vector<int>& heights) 
        {
            if (heights.empty())
            {
                return 0;
            }
    
            return largestRectangleArea(heights, 0, heights.size() - 1);
        }
    
    private:
        int largestRectangleArea(vector<int>& heights, int left, int right)
        {
            if (left < 0 || right > heights.size()-1 || left > right)
            {
                return 0;
            }
    
            if (left == right)
            {
                return heights[left];
            }
    
            int minIndex = left;
            int minHeights = heights[left];
            for (int i = left; i <= right; ++i)
            {
                if (heights[i] < minHeights )
                {
                    // 找第一个最小值
                    minHeights = heights[i];
                    minIndex = i;
                }
            }
    
            // 最小高度，矩形面积
            int minHeightArea = (right - left + 1) * minHeights;
    
            // 搜索左边最大矩形面积
            int maxLeft = minIndex - 1;
            int maxAreaLeft = largestRectangleArea(heights, left, maxLeft);
    
            // 搜索右边最大矩形面积
            int minRight = minIndex + 1;
            for (int i = minIndex + 1; i <= right && heights[i] == heights[minIndex]; ++i, ++minRight);
            int maxAreaRight = largestRectangleArea(heights, minRight, right);
    
            return max(minHeightArea, max(maxAreaLeft, maxAreaRight));
        }
    };
    
    // 解法3：栈
    // 复杂度分析
    // 时间复杂度：O(n)。
    // 空间复杂度：O(n) 。需要维持一个栈。
    //
    // 执行用时: 16 ms, 在所有 C++ 提交中击败了 75.31%的用户
    // 内存消耗 : 8.5 MB, 在所有 C++ 提交中击败了 100 % 的用户
    class Solution_3 
    {
    public:
        int largestRectangleArea(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<int>& heights, int expect)
    {
        Solution_1 s1;
        Solution_2 s2;
        Solution_3 s3;
    
        int result1 = s1.largestRectangleArea(heights);
        int result2 = s2.largestRectangleArea(heights);
        int result3 = s3.largestRectangleArea(heights);
    
        if (expect == result1 && expect == result2 && expect == result3)
        {
            cout << testName << ", solution passed." << endl;
        }
        else
        {
            cout << testName << ", solution failed. result1: " << result1 
                << ",result2: " << result2 << ",result3: " << result3 << endl;
        }
    }
    
    void Test1()
    {
        vector<int> heights;
        int expect = 0;
    
        test("Test1()", heights, expect);
    }
    
    void Test2()
    {
        vector<int> heights = { 1 };
        int expect = 1;
    
        test("Test2()", heights, expect);
    }
    
    void Test3()
    {
        vector<int> heights = { 0, 9 };
        int expect = 9;
    
        test("Test3()", heights, expect);
    }
    
    void Test4()
    {
        vector<int> heights = { 9, 0 };
        int expect = 9;
    
        test("Test4()", heights, expect);
    }
    
    void Test5()
    {
        vector<int> heights = { 1, 2, 3, 4, 5 };
        int expect = 9;
    
        test("Test5()", heights, expect);
    }
    
    void Test6()
    {
        vector<int> heights = { 5, 4, 3, 2, 1 };
        int expect = 9;
    
        test("Test6()", heights, expect);
    }
    
    void Test7()
    {
        vector<int> heights = { 1, 2, 3, 4, 5, 4, 3, 2, 1 };
        int expect = 15;
    
        test("Test7()", heights, expect);
    }
    
    void Test8()
    {
        vector<int> heights = { 2, 1, 5, 6, 2, 3 };
        int expect = 10;
    
        test("Test8()", heights, expect);
    }
    
    NAMESPACE_LARGESTRECTANGLEAREAEND
    // 测试 用例 END
    //
    
    
    void LargestRectangleArea_Test()
    {
        NAME_LARGESTRECTANGLEAREA::Test1();
        NAME_LARGESTRECTANGLEAREA::Test2();
        NAME_LARGESTRECTANGLEAREA::Test3();
        NAME_LARGESTRECTANGLEAREA::Test4();
        NAME_LARGESTRECTANGLEAREA::Test5();
        NAME_LARGESTRECTANGLEAREA::Test6();
        NAME_LARGESTRECTANGLEAREA::Test7();
    }

**执行结果：**

![20200523201815418.png][]

[https_leetcode-cn.com_problems_largest-rectangle-in-histogram]: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
[20200523200938141.png]: https://img-blog.csdnimg.cn/20200523200938141.png
[20200523201002383.png]: https://img-blog.csdnimg.cn/20200523201002383.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200523201101234.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200523201215804.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200523201235216.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200523201334656.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200523201410249.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200523201435892.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200523201455904.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200523201517288.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200523201539868.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200523201615380.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[20200523201815418.png]: https://img-blog.csdnimg.cn/20200523201815418.png