leetcode热题100（84. 柱状图中最大的矩形）c++

链接：84. 柱状图中最大的矩形 - 力扣（LeetCode）

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

思路

        我们求最大的一个矩形面积，那么如果在柱子连续递增的情况，此时最短的柱子的右长度一定是单调递增的个数了，左边的长度肯定是就是上个单调递增的值的下标到现在坐标的长度了，所以我们只需要设置一个单调栈来记录单调递增的数组的位置，要是遇到比栈顶元素小就计算，枚举一下最大值即可

代码

class Solution {
public:
    int largestRectangleArea(vector<int>& a) {
        a.push_back(0); //避免没计算，最后一个元素设置为0
        int n = a.size();
        a.insert(a.begin(),0);  //避免前面元素位置为0，不好计算
        stack<int> st; 
        int res = 0;
        for(int i=0;i<=n;i++){
            while(st.size()>1 && a[i]<a[st.top()]){ //遇到比栈顶小元素
                int cur = a[st.top()];  //当前柱子的大小
                st.pop();   //弹出
                int l = st.top();   //上个栈顶的柱子大小
                int r = i;  //遇到更小的元素的位置
                int len = r-l-1;    //长度
                //cout<<len<<" "<<cur<<endl;
                res = max(cur*len,res);
            }
            st.push(i);
        }

        return res;
    }
};