题目

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

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

image-20200911092552720

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

image-20200911092607178

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

示例:

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

题解

  1. 对于一个高度，如果能得到向左和向右的边界
  2. 那么就能对每个高度求一次面积
  3. 遍历所有高度，即可得出最大面积
  4. 使用单调栈，在出栈操作时得到前后边界并计算面积

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    stack<pair<int,int>> ans;
    int sum=0,m=0;
    int largestRectangleArea(vector<int>& heights) {
        vector<int> a;
        int sum=0;
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        //4
        for(int i=0;i<heights.size();i++){
            while(!a.empty() && heights[i]<heights[a.back()]){
                int cur = a.back();    //2
                a.pop_back();          
                int left = cur;       //2
                int right = i-1;          //3
                int s = (right-left+1) * heights[cur];
                sum = max(sum,s);
            }
            a.push_back(i);
        }
        return sum;
    }
};

参考题解

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