# 84. Largest Rectangle in Histogram

## 刷题内容

• https://leetcode.com/problems/largest-rectangle-in-histogram/

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 = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10


class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
long long ans = 0;
for(int i = 0;i < heights.size();++i)
{
int j = i + 1;
long long l,r;
for(;j < heights.size();++j)
if(heights[j] < heights[i])
{
r = (long long)heights[i] * (j - i);
break;
}
if(j == heights.size())
r = (long long)heights[i] * (heights.size() - i);
for(j = i - 1;j >= 0;--j)
if(heights[j] < heights[i])
{
l = (long long)heights[i] * (i - j - 1);
break;
}
if(j < 0)
l = (long long)heights[i] * i;
ans = max(ans,l + r);
}
return ans;
}
};


class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
long long ans = 0;
heights.push_back(0);
vector<pair<long long,int> > v;
for(int i = 0;i < heights.size();++i)
{
if(!v.size() || heights[i] > v[v.size() - 1].first)
v.push_back(make_pair(heights[i],i));
else
{
int j = v.size() - 1;
while(j > 0 && v[j].first > heights[i])
{
ans = max(ans,v[j].first * (i - v[j - 1].second - 1));
v.pop_back();
--j;
}
if(!j && v[j].first > heights[i])
{
ans = max(ans,v[j].first * (i));
v.pop_back();
}
v.push_back(make_pair(heights[i],i));
}
}
return ans;
}
};


apachecn/AiLearning