LeetCode/接雨水
给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
思路
1.暴力求解，根据每一个柱子左右两端最高的柱子，计算其蓄水量，然后把总的加起来，时间复杂度为O(n2)
点击查看代码
int trap(vector& height){
int n = height.size();
int ans = 0;
for(int i = 1;i=0;j--){
l_max = max(l_max,height[i]);
}
ans += min(l_max,r_max) - height[i];
}
return ans;
}
2.暴力求解优化，先用备忘录计算每个位置左右两端最高柱子高度，避免重复计算，时间复杂度为O(n),空间复杂度为O(n)
3.双指针，相当于算法2的进一步优化，舍去了储存两端最高高度的数组，只记录当下遍历过的左右端最高高度，之所以能这么计算，是当我们判断左边最高高度高于右边时，这时我们就能算出右边当下端点的储水量，值为右边最大高度-右边当下端点高度，然后继续移动右边端点，交替计算另一方的储水量，这样就不用把全部端点左右最大高度存储起来，以节省存储空间。
点击查看代码
class Solution {
public:
int trap(vector& height) {
int n =height.size();
int left = 0,right = n-1;
int ans = 0;
int l_max = height[0];
int r_max = height[n-1];
while(left<=right){
l_max = max(l_max,height[left]);
r_max = max(r_max,height[right]);
if(l_max 4.双指针，计算总体积，再减去柱子体积。同样矮的那端指针先移动，计算当前可容纳水的高度，若高度上升，把上升的那层体积加上，一层一层求出总体积，最后减去柱子的体积得到水的体积，时间复杂度为O(n),空间复杂度为O(1)，性能貌似比算法3好
点击查看代码
class Solution {
public:
int trap(vector& height) {
int n =height.size();
int high = 0; int buff = 0;int volume = 0;int solid = 0;
for(int i=0,j=n-1;i<=j;){
if(min(height[i],height[j])>high){
buff = min(height[i],height[j]);//暂存当前蓄水高度，因为后面还要用到之前高度做差
volume = (buff-high)*(j-i+1)+volume;//计算总体积
high = buff;
}
if(height[i]<=height[j]) i++;
else j--;
}
for(int i =0;i