学习资料：代码随想录
42. 接雨水
力扣题目链接
暴力解法超时了，直接从双指针开始
双指大概思路为创立两个数组记录两侧的最大值，这里的最大值是真正的最大的值，而不是最近的那个比较大的值，即所谓的按列计算，后面单调栈方法找到的是上一个较大值和下一个较大值，是所谓的按行计算，这样这个凹槽可能身处更大的凹槽中，所以每次都要乘一个宽度，类似与按层往上摞
class Solution {
public:int trap(vector<int>& height) {vector<int> Rightmax(height.size(),0); //牺牲一点空间复杂度换时间复杂度vector<int> Leftmax(height.size(),0);int size=height.size();Leftmax[0]=height[0];Rightmax[size-1]=height[size-1];for(int i=1;i<size;i++){Leftmax[i]=max(Leftmax[i-1],height[i]);}for(int j=size-2;j>=0;j--){Rightmax[j]=max(Rightmax[j+1],height[j]);}int sum = 0;for(int i=1;i<size-1;i++){int capacity=min(Leftmax[i],Rightmax[i])-height[i];if(capacity>0) sum+=capacity;}return sum;}
};单调栈：遇到比栈顶小的值和等于的值就入栈，相当于等待那个大的出现，如次栈顶的下一个下标对应的值比它大，再遇到大的，正好栈顶元素的两边会比其大
要注意警惕对栈非空的判断，否则超时很难排查
class Solution {
public:int trap(vector<int>& height) {stack<int> st;st.push(0);int sum = 0;for(int i=1;i<height.size();i++){if(height[i]<height[st.top()]){st.push(i);}else if(height[i]==height[st.top()]){st.push(i);} else{while(!st.empty()&&height[i]>height[st.top()]){int cur = st.top();st.pop();if(!st.empty()){ //这里还要检查一下防止访问空int h =min(height[i],height[st.top()])-height[cur];int w=i-st.top()-1;int capacity = h*w;sum+=capacity;}}st.push(i);}}return sum;}
};84.柱状图中最大的矩形
力扣题目链接
先看单调栈的方法：首先要理解求这个面积的方法是当前的值为高，宽为左边比其小到右边比其小的这个距离，高乘宽为能勾勒的最大矩形的面积
这次是找两边的小值，逻辑上是接雨水变一下操作逻辑，当前大于等于栈顶的情况入栈，等那个小的，这样栈顶两侧都比其小
尾加一个0是为了数组最后是升序的情况下，让数组到最后能找到那个小的，进行计算逻辑。最后这个0会被放在栈里，不会影响结果
开头加一个0是为了在数组降序的情况下，能找到那个小的，能进行正常的计算逻辑
class Solution {
public:int largestRectangleArea(vector<int>& heights) {stack<int> st;st.push(0);heights.insert(heights.begin(),0);heights.insert(heights.end(),0);int result =0;for(int i=1;i<heights.size();i++){if(heights[i]>heights[st.top()]){ //找的是比栈中元素小的st.push(i);}else if(heights[i]==heights[st.top()]){st.push(i);}else{while(!st.empty()&&heights[i]<heights[st.top()]){int cur = st.top();st.pop();if(!st.empty()){int left = st.top();int right = i;int h=heights[cur];int width = i-st.top()-1;result = max(result,h*width);}}st.push(i);}}return result;}
};这次双指针也是记录的下标了，而且和上一题不同的一个地方是，不是找两侧的最小的，而是找到第一个比其小的就停
// leftMinIndex[i]表示i处左边的较小高度柱子的高度的下标
class Solution {
public:int largestRectangleArea(vector<int>& heights) {vector<int> leftMinIndex(heights.size());vector<int> rightMinIndex(heights.size());int result =0;leftMinIndex[0] = -1; //初始化防止死循环for(int i=1;i<heights.size();i++){int t=i-1;while(t>=0&&heights[t]>=heights[i]){t=leftMinIndex[t]; //有回溯的感觉了}leftMinIndex[i]=t;}rightMinIndex[heights.size()-1] = heights.size(); //初始化防止死循环for(int j=heights.size()-2;j>=0;j--){int t=j+1;while(t<heights.size()&&heights[t]>=heights[j]){t=rightMinIndex[t];}rightMinIndex[j]=t;}for(int i=0;i<heights.size();i++){int area = heights[i]*(rightMinIndex[i]-leftMinIndex[i]-1);result=max(area,result);}return result;}
};
