C++刷leetcode（84. 柱状图中最大的矩形）【单调递增栈】

糖逗

题目描述：

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

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

 



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

 



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

 

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        stack<int> temp;
        heights.insert(heights.begin(), 0);//因为right = i-1为了防止越界
        heights.push_back(0);
        for (int i = 0; i < heights.size(); i++)
        {
            while (!temp.empty() && heights[temp.top()] > heights[i])
            {
                int cur = temp.top();
                temp.pop();
                int left = temp.top() + 1;
                int right = i - 1;
                ans = max(ans, (right - left + 1) * heights[cur]);
            }
            temp.push(i);

        }
        return ans;
        
    }