LeetCode 84. 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

解析：
这题的一个基本思想是以每一个bar为最低点，向左右遍历直到遇到比他小的bar或边界。这样就能找到一个以此bar为最低点的矩形面积。遍历所有的bar之后即可找到最大的矩形面积。但是向左右遍历寻找比他小的bar的时间复杂度是\(O(n)\)，在加上遍历一遍所有的bar，总的时间复杂度将为\(O(n*n)\)，是无法通过LeetCode 测试用例。因此我们需要寻找一种时间复杂度更低的寻找一个bar左右边界的算法。在网上流传了一个设计极其巧妙的方法，借助一个stack可以将时间复杂度降为O(n)。

这种算法的思想是维护一个递增的栈，这个栈保存了元素在数组中的位置。 这样在栈中每一个左边的bar都比本身小，所以左边就天然有界了，也就是左边界就是左边的一个bar。遍历一遍height数组，在将height数组入栈的时候，如果当前元素height[i]比栈顶元素小，则我们又找到了栈顶元素的右边界。因此我们在此时就可以计算以栈顶元素为最低bar的矩形面积了，因为左右边界我们都已经找到了，而且是在O(1)的时间复杂度内找到的。然后就可以将栈顶元素出栈了。这样每出栈一个元素，即计算以此元素为最低点的矩形面积。当最终栈空的时候我们就计算出了以所有bar为最低点的矩形面积。为保证让所有元素都出栈，我们在height数组最后加一个0，因为一个元素要出栈必须要遇到一个比他小的元素，也就是右边界。

具体代码如下：
[cc lang=”C++”]
class Solution {
public:
int largestRectangleArea(vector& heights) {
if(heights.size() == 0)
return 0;
heights.push_back(0);
int len = heights.size();
int ans = 0;
stack st;
for(int i=0; i < len; i++) { while(!st.empty() && heights[i] < heights[st.top()])//当前遍历的元素小于栈顶元素，出现右边界 { int val = st.top(); st.pop(); ans = max(ans, heights[val]*(i-1-(st.empty()?-1:st.top())));//当前元素为右边界，val为当前处理的bar，st.top()为左边界，计算矩形面积 } st.push(i); } return ans; } }; [/cc] 运行结果：
参考：
https://blog.csdn.net/qq508618087/article/details/50336795