给定 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
完整代码
暴力思想：针对每一组柱状图，求最大矩形，最终得出整个柱状图中的最大矩形
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int res = 0;
if(heights.size() == 0)
return res;
int cur;
for(int i = 0; i < heights.size(); ++i){
int min_height = heights[i];
for(int j = i; j < heights.size(); ++j){
if(heights[j] < min_height)
min_height = heights[j];
cur = (j - i + 1) * min_height;
if(cur > res)
res = cur;
}
}
return res;
}
};
分治
- 求当前状态下的最大矩形，最小高度左边的最大矩形，最小高度右面的最大矩形
- 递归运算，取其中的最大值
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
if(heights.size() == 0)
return 0;
return large(heights, 0, heights.size() - 1);
}
private:
int large(vector<int>& heights, int left, int right){
int min_height = left;
if(left > right)//递归终止条件
return 0;
int i = left + 1;
while(i <= right){
if(heights[i] < heights[min_height])
min_height = i;
++i;
}
int cur = (right - left + 1) * heights[min_height];
int l_cur = large(heights, left, min_height - 1);
int r_cur = large(heights, min_height + 1, right);
if(cur < l_cur)
cur = l_cur;
if(cur < r_cur)
cur = r_cur;
return cur;
}
};
栈
参考：官方题解
leetcode题解
当柱状图是升序的状态时，矩形的高度是最左边的元素，矩形的宽度越宽，矩形的面积越大。或者像【2，1，2】这种情况，矩形的长度是3高度是1。
基本思想：
当前高度的矩形最大面积如何来求？
其实也就是确定矩形的宽度，矩形的宽度为当前高度左面第一个小于当前高度的值和当前高度右面第一个小于当前高度的值之间的宽度为最大宽度
- 借助栈来保存升序状态的序列
- 从头开始遍历序列，升序时，元素入栈；一旦出现了降序，停止入栈，来计算矩形的面积
- 计算矩形的面积：
依次将栈中的元素出栈，计算以当前出栈元素为高，以当前元素出栈后的栈顶和出现降序时的元素之间作为宽（解释：当前元素出栈后的栈顶是当前元素左面第一个比当前元素小的元素，出现降序时的元素是当前元素右面第一个比当前元素小的元素），来求矩形的面积。
特别提醒：当栈中只有一个元素时，需要考虑以该元素作为矩形的高，矩形的宽是从第一个元素开始到该元素之间的宽度。
程序说明：
- 为了便于处理以矩阵中最后一个元素作为矩形的高的情况，我们在原序列的基础上添加一个元素0（0不影响最终结果，以为只当前列高是0）
- 为了便于处理当栈中只有一个元素时，以该元素作为矩形的高，矩形的宽是从第一个元素到该位置，初始时将-1（-1作为下标0之前的一个下标）入栈
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
if(heights.size() == 0)
return 0;
stack<int> st;//用来存放当前柱的下标
int res = 0, cur;
st.push(-1);// 便于处理以第一个元素作为矩形面积一部分的情况
heights.push_back(0);//便于处理以最后一个元素作为矩形面积一部分的情况
for(int i = 0; i < heights.size(); ++i){
while(st.top() != -1 && heights[i] < heights[st.top()]){
int j = st.top();
st.pop();
cur = heights[j] * (i - st.top() - 1);//宽度为当前不满足升序情况的元素和出栈元素的上一个元素之间的宽度
if(cur > res)
res = cur;
}
st.push(i);
}
return res;
}
};