最后两题了，直接上题目。

题目：接雨水

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 个单位的雨水（蓝色部分表示雨水）。

 题目分析：

        这一题呢，可以使用暴力解法，双指针解法，和单调栈解法。本质上都是对每一个下标求左边第一个大于他的和右边第一个大于它的。为什么呢？就像一个木桶一样，确定底部之后，能装多少水取决于最短的那块板。所以在确定边界之后，最小的板和底部的差值就是能装的水了。

        不过我们需要确定，装水的多少按行还是按列。

按照行来计算如图： 

按照列来计算如图： 

以下就以按列来计算。大概的思路就是这样

 

具体的暴力解法如下，显然超时了，不过可以使用双指针优化。

public class Solution {public int Trap(int[] height) {int res=0;for(int i=0;i<height.Length;i++){if(i==0||i==height.Length-1) continue;int rHeight = height[i]; // 记录右边柱子的最高高度int lHeight = height[i]; // 记录左边柱子的最高高度for (int r = i + 1; r < height.Length; r++) {if (height[r] > rHeight) rHeight = height[r];}for (int l = i - 1; l >= 0; l--) {if (height[l] > lHeight) lHeight = height[l];}int h =Math.Min(rHeight,lHeight)-height[i];if(h>0) res+=h;}return res;}
}

单调栈解法

public class Solution {public int Trap(int[] height) {int res=0;if(height.Length<=2) return 0;Stack<int> st=new Stack<int>();st.Push(0);for(int i=1;i<height.Length;i++){while(st.Count>0&&height[i]>height[st.Peek()]){int mid=st.Peek();st.Pop();if(st.Count>0){int h=Math.Min(height[st.Peek()],height[i])-height[mid];int w=i-st.Peek()-1;res+=h*w;}}st.Push(i);}return res;}
}

题目：柱状图中最大的矩形

84. 柱状图中最大的矩形 - 力扣（LeetCode）

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

 题目分析：

        这一题和上一题很相似，需要注意的是，接雨水需要木板高于底部，那么求面积呢？显然需要找到低于当前位置的左右边界，在边界内部才能取到最大面积（注意，不包括边界）。暴力和双指针解法和上面的一样，这里就不赘述了。

        既然我们找的是左右两边小于该值的，那么单调栈里面就应该是从栈顶到栈底递减的。所以就会出现一种情况，假设nums={4,3,2,1},入栈之后顺序保持不变，那就走不到我们求面积的逻辑里面了，所以我们给数组的两边都加上一个0，让它一定会出现增减。看看具体的实现。

public class Solution {public int LargestRectangleArea(int[] heights) {int res=0;Stack<int> st=new Stack<int>();int [] newHeights = new int[heights.Length + 2];Array.Copy(heights,0,newHeights,1,newHeights.Length-2);st.Push(0);for(int i=1;i<newHeights.Length;i++){while(newHeights[i]<newHeights[st.Peek()]){int mid=st.Peek();st.Pop();int left=st.Peek();int right=i;int cur=((right-left)-1)*newHeights[mid];res=Math.Max(cur,res);}st.Push(i);}return res;}
}

对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。

代码随想录 (programmercarl.com)

已刷题目：130