C语言重构【84】柱状图中最大的矩形

港控/mmm° 2023-01-05 14:18 195阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码： ####

*  [Git地址][Git]

#### 题目 ####

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

![在这里插入图片描述][20210112234646497.png]

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

![在这里插入图片描述][20210112234656557.png]

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
    示例:
    输入: [2,1,5,6,2,3]
    输出: 10

#### 方案： ####

*  虽然可以过，但有大问题

class Solution
    { 
    public:
        int largestRectangleArea(vector<int> &heights)
        { 
            //栈的思想
            stack<int> s;
            //哨兵1、2号
            heights.insert(heights.begin(), 0);
            heights.push_back(0);
            s.push(0);
            int len = heights.size();
            int area = 0;
            int width = 0;
            int index;
    
            //第一遍遍历
            //当前比前一个大，前一个暂时无法判断最大值，入栈
            //当前比前一个小，前一个可以判断最大值，出栈
            for (int i = 1; i < len; i++)
            { 
                while (heights[i] < heights[s.top()])
                { 
                    //计算面积，弹栈
                    index = s.top();
                    s.pop();
    
                    //弹出来的元素的len=前后俩元素的间隔，高度就是本下标的高度
                    width = i - index;
                    // 这里有优化空间,大问题
                    int j = index - 1;
                    while (j > 0 && heights[j--] > heights[index])
                        width++;
                    area = max(area, heights[index] * width);
                }
                s.push(i);
            }
            //最后返回最大值
            return area;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n2)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode
[20210112234646497.png]: /images/20221119/a027029db9d449d3b92494d2e59c5e2c.png
[20210112234656557.png]: /images/20221119/430ceffc06d34014ada87ce98764f71f.png