84.柱状图中最大的矩形

思路一：单调栈

class Solution {
public:int largestRectangleArea(vector<int>& heights) {heights.insert(heights.begin(),0);//头加0，防止刚开始heights.push_back(0);//尾巴上加0，防止一直递增最后丢失数据int n=heights.size();stack<int>st;st.push(0);int res=0;for(int i=1;i<n;i++){while(heights[i]<heights[st.top()]){int mid=st.top();//找到右边第一个比自己小的数st.pop();int w=i-st.top()-1;int h=heights[mid];res=max(res,w*h);}st.push(i);}return res;}
};