【leetcode刷题】T22-柱状图中最大的矩形
【英文题目】（学习英语的同时，更能理解题意哟~）
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height =[2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area =10unit.
Example:
Input: [2,1,5,6,2,3]
Output: 10
【中文题目】
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
【思路】
这道题，暴力破解，遍历所有元素，得到包含该元素在内的所有右区间的矩阵面积，时间复杂度O(n^2)，不能通过。比如[2, 1, 5, 6, 2, 3]，遍历所有右区间[2], [2, 1], [2, 1, 5], …, [2, 1, 5, 6, 2, 3], [1], [1, 5], [1, 5, 6], …, [1, 5, 6, 2, 3], [5], [5, 6], …, [5, 6, 2, 3], …, [3]，得到各自的矩阵面积，返回最大值。
使用栈的方法，我看了答案也琢磨了很久。
对于[2, 1, 5, 6, 2, 3]，由于1(heights[1]) < 2(heights[0])，区间[1]根本不用计算面积，肯定小于区间[2, 1]；同理，由于2(heights[4]) < 6(heights[3])，区间[2]不用计算；由于2(heights[4]) < 5(heights[2])，区间[5, 6, 2]不用计算，肯定小于矩阵[5, 6]的矩阵面积……
是不是有一点启发？要是遍历所有元素时，有一个栈存储左区间的元素，并且栈顶元素到栈底元素始终由大到小，每遍历一个元素heights[i]，如果栈为空，直接压栈；否则判断其与栈顶元素的大小关系，如果heights[i]较大，压栈，反之弹出栈顶元素，计算矩阵面积，循环遍历heights[i]和栈顶元素的大小关系进行操作，直到栈为空或者该元素小于栈顶元素。
（可能解释还不够清楚，那就直接看代码吧~）
【代码】
python版本
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
heights.append(-1)
stack = []
res =
for i, h in enumerate(heights):
while(len(stack) > and h <= heights[stack[-1]]):
a = heights[stack.pop()]
j = stack[-1] if len(stack) > else -1
# print(a, i-j-1)
res = max(res, a * (i-j-1))
stack.append(i)
return res
C++版本
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> ls;
int res = ;
heights.push_back(-1);
for(int i=; i < heights.size(); i++){
while(ls.size() > && heights[i] <= heights[ls.top()]){
int a = heights[ls.top()];
ls.pop();
int j = -1;
if(ls.size() > )
j = ls.top();
if(res < a * (i - j - ))
res = a * (i - j - );
}
ls.push(i);
}
return res;
}
};腾讯云开发者
