题目描述:

难度困难827

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

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

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

解法一: 枚举底

需要注意的是一根柱子的面积是它的高,不是0;

int largestRectangleArea(vector
   
    & heights) {	int length = heights.size();    int area = 0;        //枚举左边底    for (int i = 0; i < length ; ++i) {		int minHeight = INT_MAX;        //枚举右边底        for (int j = i;j < length ; ++j) {            //每次都要计算它的面积        	minHeight = min(minHeight,heights[j]);            area = max(area,(j - i + 1) * minHeight);        }    }        return area;}

时空复杂度分析

时间复杂度: 为O(N^2);因复杂度较高会超出运行时间限制;

空间复杂度: 为O(1);

解法二.枚举高

这个方法虽然也是会超出运行时间限制,但是单调栈是基于这个思想来的,我也思考了很久,

int largestRectangleArea(vector
   
    & heights) {        int n = heights.size();        int area = 0;                //以mid为中点left和right分别向左右引伸找到 left - 1 < height[mid] 和 right + 1 < height[mid] 停止    	//这样的话left 和 right之间的高度就height[mid]最小了        //不用经常去算面积了    //枚举高mid 是heights数组的下标;        for (int mid = 0; mid < n; ++mid) {                        int left = mid, right = mid;                // 确定左右边界            while (left - 1 >= 0 && heights[left - 1] >= heights[mid]) --left;                        while (right + 1 < n && heights[right + 1] >= heights[mid]) ++right;                        // 计算面积            area = max(area, (right - left + 1) * heights[mid]);        }        return area;    }

时空复杂度分析

时间复杂度: 为O(N^2);因复杂度较高会超出运行时间限制;

空间复杂度: 为O(1);

解法三: 单调栈

这位老哥的题解就相当不错:

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-by-ikaruga/

也可以看一下官方题解;

int largestRectangleArea(vector
   
    & heights){    int ans = 0;    vector
    
      st;    heights.insert(heights.begin(), 0);    heights.push_back(0);    for (int i = 0; i < heights.size(); i++)    {        while (!st.empty() && heights[st.back()] > heights[i])        {            int cur = st.back();            st.pop_back();            int left = st.back() + 1;            int right = i - 1;            ans = max(ans, (right - left + 1) * heights[cur]);        }        st.push_back(i);    }    return ans;}作者：ikaruga链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-by-ikaruga/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。