42.接雨水

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

过程

发现有特殊情况就是，最高峰的地方，如果右边小于他，然后再右边也都很小的话，并不会存雨水，就是两边都要有边界。然后就想了一种思路，就是找凹陷。

class Solution {
public:int trap(vector<int>& height) {int l=0;//l和r来保存左右边界int r=1;int n=height.size();int room=0;//用来存储雨水while(height[l]==0){l++;r=l+1;}//找到第一个左边界while(r<n){if(height[r]<height[l]){//继续搜索凹陷r++;}else if(height[r]>height[l]){//找到了凹陷，计算roomfor(int i=l+1;i<r;i++){room+=height[l]-height[i];}l=r;r++;}else{if(r-l==1){//如果相邻l=r;r++;}else{//找到了凹陷，计算roomfor(int i=l+1;i<r;i++){room+=height[l]-height[i];}l=r;r++;}}}return room;}
};

第二个用例对了，第一个有问题

应该是右边界的问题，如果一直找不到右边等高的，那就直接执行完了。没有考虑到局部凹陷的情况。

解法

class Solution {
public:int trap(vector<int>& height) {int ans = 0;int left = 0, right = height.size() - 1;int leftMax = 0, rightMax = 0;while (left < right) {leftMax = max(leftMax, height[left]);rightMax = max(rightMax, height[right]);if (height[left] < height[right]) {ans += leftMax - height[left];++left;} else {ans += rightMax - height[right];--right;}}return ans;}
};

这个思路就是克服了我上面那个忽略了局部的问题，因为我的r也是从左边开始遍历的，不可能先遍历到最右边再找有没有边界。r从最右边开始，
如果左边小于最右边，那么就是假设从左边开始算存雨水的量。因为之前做过一个题是木桶理论，存水量取决于短板。所以要从小的一边开始遍历。然后还有两个leftmax和rightmax来保存局部的存水量。因为只要左边小于右边，那一定可以存到水。