42. 接雨水 - 力扣（LeetCode）
思路：单调栈，第一个是比栈顶大的是右边界，栈顶元素是底，出栈后下一个栈顶元素是左边界。
使用左右边界最小值与中间元素相减算出高度，右边界减左边界减1算出宽度
1.双指针
class Solution {
public:int trap(vector<int>& height) {int n=height.size();int ans=0;vector<int>left(n);vector<int>right(n);//左边第一个的左边最大数为0for(int i=1;i<n;i++){left[i]=max(left[i-1],height[i-1]);//预处理当前数左边的最大数}//右边第一个的右边最大数为0for(int i=n-2;i>=0;i--){right[i]=max(right[i+1],height[i+1]);//预处理当前数右边的最大数}for(int i=1;i<n-1;i++){int t=min(left[i],right[i]);//取最小的if(t>height[i]){//大于当前就算出可以接的雨水数量ans+=t-height[i];}}return ans;}
};2.单调栈
class Solution {
public:int trap(vector<int>& height) {int n=height.size();int ans=0;stack<int>st;st.push(0);for(int i=1;i<n;i++){while(!st.empty()&&height[i]>height[st.top()]){int mid=height[st.top()];//记录中间值st.pop();if(st.empty()){break;}int h=min(height[i],height[st.top()])-mid;//算出高度int w=i-st.top()-1;//减一算出宽度ans+=w*h;}st.push(i);} return ans;}
};84. 柱状图中最大的矩形 - 力扣（LeetCode）
思路：同上，只是换成单调递减栈。以中间值为高度，右边界减左边界减1算出宽度。选最大的值
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int ans=0;stack<int>st;//添加前导0和后导0判断原数组单调递增和单调递减的情况heights.insert(heights.begin(),0);heights.push_back(0);st.push(0);//注意是增加前导0和后导0的数组大小for(int i=1;i<heights.size();i++){//判断当前左右比当前小的值作为边界，当前数为高度while(heights[i]<heights[st.top()]){//单调递减int mid=st.top();st.pop();int w=i-st.top()-1;int h=heights[mid];ans=max(ans,w*h);}st.push(i);}return ans;}
};总结
单调栈。在解决左边更大或右边更大的问题可以考虑单调栈方法