刷题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]；
| heights[i] | 栈中元素下标 | 当前矩形最大面积 | 操作情况 |
| heights[0] = 0 | s = [0] | 0 | 0入栈 |
| heights[1] = 2 | s = [0,1] | 0 | 1入栈 |
| heights[2]=1 < 2 | s=[0] | 2 |
栈顶元素1出栈 面积= 2*(2-0-1)=2 |
| heights[3]=5 | s=[0,2,3] | 2 | 3入栈 |
| heights[4]=6 | s=[0,2,3,4] | 2 | 4入栈 |
| heights[5]=2<heights[4]=6 | s=[0,2,3] | 6 |
4出栈 面积= 6*(5-3-1) = 6 |
| heights[5]=2<heights[3]=5 | s=[0,2] | 10 |
3出栈 面积= 5*(5-2-1) = 10 |
| 2>heights[2]=1 | s=[0,2,5] | 10 | 5入栈 |
| heights[6]=3 | s=[0,2,5,6] | 10 | 6入栈 |
| heights[7]=0 < heights[6]=3 | s=[0,2,5] | 10 |
6出栈 面积= 3*(7-5-1) = 3 |
| heights[7]=0< heights[5]=2 | s=[0,2] | 10 |
5出栈 面积= 2*(7-2-1) = 8 |
| heights[7]=0< heights[2]=1 | s=[0] | 10 |
2出栈 面积= 1*(7-0-1) = 6 |
| heights[7]=0 | s=[0,7] | 输出10 |
完整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;}
};
