题目描述

给定 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法1

(单调栈)

时间复杂度o(n)

参考文献

C++ 代码

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n,0), right(n,0);
        stack<int> st;
        for(int i=0; i<n; ++i){//先求左边，距离最近的 小于它的数的位置
            while(!st.empty() && heights[i] <= heights[st.top()]) st.pop();
            if(st.empty()) left[i] = -1;
            else left[i] = st.top();
            st.push(i);
        }

        while(!st.empty()) st.pop();

        for(int i=n-1; i>=0; --i){//求右边，距离最近的 小于它的数的位置
            while(!st.empty() && heights[i] <= heights[st.top()]) st.pop();
            if(st.empty()) right[i] = n;
            else right[i] = st.top();
            st.push(i);
        }

        //计算面积
        int res = 0;
        for(int i=0; i<n; ++i){
            int temp = heights[i] * (right[i] - left[i] - 1); //取出两个位置之间的长度作为 长
            res = max(res, temp);
        }
        return res;
    }
};