找每个柱子左右两边第一个小于该柱子的柱子，栈头到栈底的顺序应该从大到小

求解矩形面积需要分别得到该柱左边和右边高度小于本柱的柱子

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int res = 0;stack<int>st;heights.insert(heights.begin(),0);heights.push_back(0);st.push(0);for(int i = 1;i < heights.size();i++){if(heights[i] >= heights[st.top()]){st.push(i);}else{//此时新柱子的高度小于栈顶柱子，作为栈顶柱子右边的柱子while(!st.empty() && heights[i] < heights[st.top()]){//确保单调栈从大到小int mid = st.top();st.pop();int l = st.top();//由单调递减栈的性质可知栈中存放的其他柱子的高度都比栈顶柱子底，此柱子可以作为原栈顶柱子左边的柱子int r = i;int w = r - l - 1;//计算出宽度int h = heights[mid];//新柱子的高度res = max(res,h * w);}st.push(i);}}return res;}
};

时间复杂度O(n)

空间复杂度O(n)