接雨水（双指针做法 详细思路）
题目来源
题目描述
给定
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提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
题目限制
要求做法是双指针，最优解
思路分析（双指针思路怎么来的？）
这道题目呢，其实说实话，我第一次做是看答案的，自己做感觉很难能够想的出来，而我又看了好多的讲解，得出一个结论：
大家看答案不一定能够真的懂，就大部分题解，都讲解的是纯代码的内容，他没有讲到本质的逻辑，这样的话会造成大家对这道题影响不深刻，没有真正本质上理解，所以说我就给大家讲讲这个底层的逻辑
我们从最左边开始模拟，
左边第一个位置，当前位置高度是0，上界也是0，那么能接的雨水量就是上界减去当前高度，得到0.
左边第二个位置，当前位置高度是1，上界从上次的0，更新为当前的1，即当前高度就是上界，因此，能接的雨水量就是上界减去当前高度，得到0。
左边第三个位置，当前位置高度是0，上界保留上次的1，则，能接的雨水量就是上界减去当前高度，得到1.
左边第四个位置，同第二个位置，上界更新为2，能接的雨水量为0
左边第五个位置，能接的雨水量：上界2-当前高度1=1
左边第六个位置，能接的雨水量：上界2-当前高度0=2
左边第七个位置，能接的雨水量：上界2-当前高度1=1
左边第八个位置，上界更新为3，能接的雨水量：上界3-当前高度3=0
左边第九个位置，能接的雨水量：上界3-当前高度2=1
但是！由图可知，这个位置如果要能接水1，那么右侧就应该有比当前位置更高的一个边界，可以把水接住，否则就会从右侧漏掉！
因此，单纯的从左往右是不行的——所以我们用双指针
在我红框框起来的这一部分，我们可以知道：实际上， 1、2、3这三个位置，他们的接水量是由左右两边决定的，而且，决定“上界”（上界就是2，再降雨的话就会从左边边界漏出）的是左右两边较小的边界。
所以说，我们就以这个局部图为例子：
编号1 2 3 4 5
既然我们要用双指针，那么我们就先定义一下：left=1 right=5
此时，左右上界分别为2 3
因为上面我们已经分析过，小的那个上界才决定能接多少水，所以我们从左边开始
（假设从右边开始的话，加入3位置高度是2呢，那你4的位置接水量=右边上界3-当前位置1=2，但是实际为1，就是因为这样的话，左边就会漏掉，所以说接水会接不住，所以我们从较小的上界开始）
之后的内容就和上面模拟的是一样的
具体代码
class Solution {
public:
int trap(vector<int>& height) {
int ys=0;
int l=0,r=height.size()-1;
int lup=0,rup=0;
while(l<r)
{
lup=max(lup,height[l]);
rup=max(rup,height[r]);
if(height[l]<height[r])ys+=lup-height[l++];
else ys+=rup-height[r--];
}return ys;
}
};代码解释
首先，定义了几个变量：
ys表示接收雨水量，初始化为0
l就是left，代表左边的当前位置
r就是right，代表右边的当前位置
lup就是leftup，代表左边的上界
rup就是rightup，代表右边的上界
然后，第一步，比较，得出左右上界的值是多少？也就是max值和当前高度比较，取大的那个：
lup=max(lup,height[l]);
rup=max(rup,height[r]);
第二步，判断谁起决定性作用，左边当前位置和右边当前位置比较，取小的那个方向，进行操作，左边的话就是左上界减去当前左边高度，右边的话同理，右上界减去当前右边高度：
if(height[l]<height[r])ys+=lup-height[l++];
else ys+=rup-height[r--];
第三步，while循环结束，左边操作位置和右边操作位置重合：
所以循环语句是while(l<r)
最后，返回一下接收水量ys即可：
return ys；
注意事项
我们在做这道题的时候，脑子里一定要有思路，而不是对于代码解释的简单吸收和模拟，要知道这样做的底层逻辑是什么，知道了原理，就不容易忘，下次还能做出来，一定要培养自己对于这道题的思路
总结要点
最后我再来总结一下这道题解题要点：
1.知道“上界”是什么？
2.每个位置的接收雨水量的计算公式要知道：接收雨水量=当前的上界-当前高度
3.除了知道当前位置的接收雨水量计算公式，目光还不能局限于就这当前一个位置，而要看左右，如果说发生了漏水情况怎么办？
4.因此，要对于左右的最大值进行比较，从较小的上界处开始操作，如果选了大的那个，那么在后续位置操作时就有可能漏水，从较小的上界那一侧漏出去了
知道了这四点，我们就能够把整个代码理顺，搞清楚底层逻辑，不容易忘记
另外，这是腾讯的面试题，据说连腾讯公司里面的保洁阿姨和保安大哥都会做呢！不会做的要加油啦！😄
原文地址：https://blog.csdn.net/ajsjnnn/article/details/144328348
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！