42. 接雨水(超经典款）
42. 接雨水 - 力扣（LeetCode）
给定
n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。示例 2：
输入：height = [4,2,0,3,2,5] 输出：9
双指针法（优先掌握）
在暴力解法中，我们可以看到只要记录左边柱子的最高高度 和 右边柱子的最高高度，就可以计算当前位置的雨水面积，这就是通过列来计算。
当前列雨水面积：min(左边柱子的最高高度，记录右边柱子的最高高度) - 当前柱子高度。
当前位置，左边的最高高度是前一个位置的左边最高高度和本高度的最大值。
即从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);
从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);
class Solution {
public:
//双指针法int trap(vector<int>& height) {if(height.size()<=2)return 0;vector<int>maxleft(height.size(),0);vector<int>maxright(height.size(),0);int size=height.size();//记录每个柱子左边柱子的最大值maxleft[0]=height[0];for(int i=1;i<size;i++){maxleft[i]=max(height[i],maxleft[i-1]);}//记录每个柱子右边柱子的最大值maxright[size-1]=height[size-1];for(int i=size-2;i>=0;i--)maxright[i]=max(maxright[i+1],height[i]);//求所有雨水的面积和int sum=0;for(int i=0;i<size;i++){int count=min(maxleft[i],maxright[i])-height[i];if(count>0)sum+=count;}return sum;}
};单调栈
单调栈就是保持栈内元素有序。和栈与队列：单调队列 (opens new window)一样，需要我们自己维持顺序，没有现成的容器可以用。
通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。
而接雨水这道题目，我们正需要寻找一个元素，右边最大元素以及左边最大元素，来计算雨水面积。
首先，
其次，从栈顶到栈底是从小到大，因为求的是右边第一个比当前元素大的元素。
我们要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。
如图所示：
- 栈里要保存什么数值
栈里就存放下标就行，想要知道对应的高度，通过height[stack.top()] 就知道弹出的下标对应的高度了。
单调栈处理逻辑
- 情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度 height[i] < height[st.top()]
- 情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度 height[i] == height[st.top()]
- 情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度 height[i] > height[st.top()]
如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了，如图所示：
栈顶元素弹出，凹槽的底部，也就是中间位置，下标记为mid，对应的高度为height[mid]（图中的高度1）。
栈顶元素st.top()，就是凹槽的左边位置，下标为st.top()，对应的高度为height[st.top()]（图中的高度2）。
当前遍历的元素i，就是凹槽右边的位置，下标为i，对应的高度为height[i]（就是图中的高度3）。
其实就是栈顶和栈顶的下一个元素以及要入栈的元素，三个元素来接水！
那么雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度，代码为：
int h = min(height[st.top()], height[i]) - height[mid];雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度），代码为：
int w = i - st.top() - 1 ;当前凹槽雨水的体积就是：
h * w。
代码
class Solution {
public:
//单调栈法int trap(vector<int>& height) {if(height.size()<=2)return 0;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{while(!st.empty()&&height[i]>height[st.top()]){int mid=st.top();st.pop();if(!st.empty()){int h=min(height[st.top()],height[i])-height[mid];//求高度int w=i-st.top()-1;//求宽带sum+=h*w;}}st.push(i);//怎么老是忘记这一个，要记得加入新的元素下标啊啊}}return sum;}
};84.柱状图中最大的矩形
84. 柱状图中最大的矩形 - 力扣（LeetCode）
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10示例 2：
输入： heights = [2,4] 输出： 4
双指针法（难理解）
class Solution {
public:int largestRectangleArea(vector<int>& heights) {vector<int> minLeftIndex(heights.size());vector<int> minRightIndex(heights.size());int size = heights.size();// 记录每个柱子 左边第一个小于该柱子的下标minLeftIndex[0] = -1; // 注意这里初始化，防止下面while死循环for (int i = 1; i < size; i++) {int t = i - 1;// 这里不是用if，而是不断向左寻找的过程while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];minLeftIndex[i] = t;}// 记录每个柱子 右边第一个小于该柱子的下标minRightIndex[size - 1] = size; // 注意这里初始化，防止下面while死循环for (int i = size - 2; i >= 0; i--) {int t = i + 1;// 这里不是用if，而是不断向右寻找的过程while (t < size && heights[t] >= heights[i]) t = minRightIndex[t];minRightIndex[i] = t;}// 求和int result = 0;for (int i = 0; i < size; i++) {int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);result = max(sum, result);}return result;}
};单调栈法
因为本题是要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序！
我来举一个例子，如图：
只有栈里从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。
所以本题单调栈的顺序正好与接雨水反过来。
栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int result=0;//从栈顶到栈顶的顺序是从大到小stack<int>st;//存元素下标heights.insert(heights.begin(),0);//数组头部和尾部加入0heights.push_back(0);st.push(0);for(int i=1;i<heights.size();i++){if(heights[i]>=heights[st.top()])//如果当前柱子的高度 heights[i] 大于或等于栈顶柱子的高度 heights[st.top()]，则将当前柱子的索引 i 压入栈中。st.push(i);//情况一和二结合体else{while(!st.empty()&&heights[i]<heights[st.top()]){int mid=st.top();st.pop();//弹出栈顶元素 mid，这代表了我们正在考虑的柱子。if(!st.empty()){int left=st.top();//获取当前栈顶元素，即左边界的索引。int right=i;//当前索引 i 作为右边界。int w=right-left-1;int h=heights[mid];result=max(result,w*h);}}st.push(i);}}return result;}
};如果要深刻理解的话，记得要模拟一遍代码哦。
