题目描述
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.
Example1:
Input: [2,1,5,6,2,3] Output: 10
解题思路
- 参考
- 维护一个递增的栈，这个栈保存了元素在数组中的位置。
- 这样在栈中每一个左边的bar都比本身小，所以左边就天然有界了，也就是左边界就是左边的一个bar。
- 遍历一遍height数组，在将height数组入栈的时候，如果当前元素height[i]比栈顶元素小，则我们又找到了栈顶元素的右边界。
- 因此我们在此时就可以计算以栈顶元素为最低bar的矩形面积了，因为左右边界我们都已经找到了，而且是在O(1)的时间复杂度内找到的。
- 然后就可以将栈顶元素出栈了。
- 这样每出栈一个元素，即计算以此元素为最低点的矩形面积。当最终栈空的时候我们就计算出了以所有bar为最低点的矩形面积。
- 为保证让所有元素都出栈，我们在height数组最后加一个0，因为一个元素要出栈必须要遇到一个比他小的元素，也就是右边界。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
if(heights.size() == 0){
return 0;
}
heights.push_back(0);
int size = heights.size();
int res = 0;
stack<int> s;
for(int i = 0; i < size; i++){
while(!s.empty() && heights[i] < heights[s.top()]){
auto val = s.top();
s.pop();
res = max(res, heights[val] * (i - 1 - (s.empty() ? -1 : s.top())));
}
s.push(i);
}
return res;
}
};
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int ans = 0;
stack<int> st;
heights.insert(heights.begin(), 0);
heights.push_back(0);
for(int i = 0; i < heights.size(); i++){
while(!st.empty() && heights[st.top()] > heights[i]){
int cur = st.top();
st.pop();
int left = st.top() + 1;
int right = i - 1;
ans = max(ans, (right - left + 1) * heights[cur]);
}
st.push(i);
}
return ans;
}
};
