文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Largest Rectangle in Histogram
2. Solution
- O(N^2)
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int maxArea = 0;
for(int i = 0; i < heights.size(); i++) {
int left = i;
int right = i;
for(left = i; left >= 0; left--) {
if(heights[left] < heights[i]) {
break;
}
}
for(right = i; right < heights.size(); right++) {
if(heights[right] < heights[i]) {
break;
}
}
int area = (right - 1 - left - 1 + 1) * heights[i];
if(area > maxArea) {
maxArea = area;
}
}
return maxArea;
}
};
- O(N)
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int maxArea = 0;
stack<int> border;
heights.push_back(0);
for(int i = 0; i < heights.size(); i++) {
if(border.empty() || heights[i] > heights[border.top()]) {
border.push(i);
}
else {
int index = border.top();
border.pop();
int area = heights[index] * (border.empty()?i:i - border.top() - 1);
if(area > maxArea) {
maxArea = area;
}
i--;
}
}
return maxArea;
}
};
