84. Largest Rectangle in Histogram
难度:Hard
刷题内容
原题连接
- 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
思路1 **- 时间复杂度: O(n^2)*- 空间复杂度: O(n)***
这题第一种思路就是用暴力的方法去解。时间复杂度为O(n^2)。遍历数组，对数组中每个元素分别向右向左找到最远，计算最大值得到结果
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;
}
};
思路2 **- 时间复杂度: O(n)*- 空间复杂度: O(n)***
上面第一种方法的实现中有重复计算的过程，我们用栈去解决这个问题就很好的剔除了重复计算的过程，时间复杂度降到了O(n)。先定义一个栈，我们要保证栈中的数是递增的，遍历数组，若这个数小于栈顶的数，则将栈顶的数弹出，并计算栈顶元素的最大距离，直到栈为空或者比这个数小
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;
}
};
