刷题day54：柱形图中最大矩形

题意描述：

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

 暴力方法：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int result = 0;
        for(int i = 0; i < n; i++){
            int height = heights[i];
            int left = i, right = i;
            while(left - 1 >= 0 && heights[left - 1] >= height){
                left--;
            }
            while(right + 1 < n && heights[right + 1] >= height){
                right++;
            }
            result = max(result, (right - left + 1) * height);
        }
        return result;
    }
};

复杂度为O(n*n)。会超时

利用单调栈思路：

首先单调栈的代码如下：

stack<int> st;
for(int i = 0; i < nums.size(); i++)
{
	while(!st.empty() && st.top() > nums[i])
	{
		st.pop();
	}
	st.push(nums[i]);
}

单调栈：维护一个单独递增的栈，只有放入元素比栈顶元素大才入栈，否则一直pop +计算最大面积。栈中初始化一个0，数组的末尾添加一个元素0，这样才能计算所有的情况（或者说清空栈）。

以heights = [2,1,5,6,2,3]为例说明：.

加入0后heights =  [0, 2,1,5,6,2,3, 0]；

完整C++代码如下：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int result = 0;
        heights.insert(heights.begin(), 0);
        heights.emplace_back(0);
        for(int i = 0; i < heights.size(); i++){
            while(!st.empty() && heights[st.top()] > heights[i]){
                int height = heights[st.top()];
                st.pop();
                int width = i - st.top() - 1;
                result = max(result, height * width);
            }
            st.push(i);
        }
        return result;
    }
};