42. 接雨水
class Solution {
public:int trap(vector<int>& height) {int n=height.size(), sum=0;vector<int> max_left=height, max_right=height;for(int i=1; i<n; i++){max_left[i]=max(max_left[i-1],max_left[i]);}for(int i=n-2; i>=0; i--){max_right[i]=max(max_right[i],max_right[i+1]);}for(int i=0; i<n; i++){int cur=min(max_left[i],max_right[i])-height[i];if(cur>0)sum+=cur;}return sum;}
};双指针解法：
max_left[i]：第i个元素以左(包含第i个)，所有元素的最大值
max_right[i]：第i个元素以右(包含第i个)，所有元素的最大值
按列统计雨水容量，每列可装的雨水高度：min(max_left[i],max_right[i])-height[i]
84. 柱状图中最大的矩形
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int n=heights.size(),max_area=INT_MIN;stack<int> st;vector<int> left(n,-1);vector<int> right(n,n);for(int i=0; i<n; i++){while(!st.empty()&&heights[i]<heights[st.top()]){right[st.top()]=i;st.pop();}st.push(i);}st=stack<int>();for(int i=n-1; i>=0; i--){while(!st.empty()&&heights[i]<heights[st.top()]){left[st.top()]=i;st.pop();}st.push(i);}for(int i=0; i<n; i++){int cur=heights[i]*(right[i]-left[i]+1-2);max_area=max(max_area,cur);}return max_area;}
};尝试所有可能的中心高度，累计最大值。选定heights[i]作为中心，向两边膨胀得到最大面积，当遇到第一个比它小的元素时，则不可继续膨胀（否则会以更小的这个元素为中心，而不是heights[i]),也就是问题转化为求【下一个更小元素】的问题，参考上一篇博客，经典的单调栈解法。
从前往后扫，得到右侧第一个更小；
从后往前扫，得到左侧第一个更小。
注意，left和right的元素时取不到的，所以计算宽度时要减2。