力扣HOT100之双指针42.-接雨水
力扣HOT100之双指针：42. 接雨水
这道题在之前刷代码随想录的时候做过，果然现在又不记得了，当时是用单调栈做的，现在忘得一干二净，难绷。。。
单调栈的思路不是本文的重点，单调栈的思路可以参考我的
这道题我用双指针想不出来,然后去看灵神的题解了，学到了一种用前后缀解决的新办法，有必要记录一下。
前后缀解法
我们可以认为每一个柱子都与相邻的两根柱子组成一个水桶，当中间的柱子比两边的柱子低时，则可以留住雨水，当然，当多个柱子排列在一起时，只需要满足当前柱子的两侧（不一定是相邻的柱子）都有比自己高的柱子时，就能留住雨水，而当前位置能留住多少雨水，则取决于两侧较短的柱子与当前柱子之间的高度差，因此我们需要额外定义两个数组，一个用来存储每一个柱子及其前面的柱子中的最大高度，
prefix[i]
则表示从下标为0到下标为i的柱子中的最大高度，同理，定义另一个数组用来存储每一个柱子及其后面的柱子中的最大高度，
suffix[i]
则表示从下标为
i
到
height[height.size() - 1]
的柱子中的最大高度。然后从前往后遍历记录
prefix[i]
，从后往前记录
suffix[i]
.
然后再从前往后遍历一遍柱子，只有满足
height[i] < prefix[i] && height[i] < suffix[i]
时才能留住雨水，该柱子处能留住的雨水量为
min(prefix[i], suffix[i]) - height[i]
，单调栈是横着计算雨水量，而前后缀法则是竖着计算雨水量，非常生动贴切。
class Solution {
public:
int trap(vector<int>& height) {
int result = 0;
vector<int> prefix(height.size(), 0); //用来记录前缀(从下标为0到i的最大高度)
vector<int> suffix(height.size(), 0); //用来记录后缀(从下标为i到height.size() - 1的最大高度)
prefix[0] = height[0];
suffix[height.size() - 1] = height[height.size() - 1];
for(int i = 1; i < height.size(); i++) //记录每一个位置的最大前缀
prefix[i] = max(prefix[i - 1], height[i]);
for(int i = height.size() - 2; i >= 0; i--) //记录每一个位置的最大后缀
suffix[i] = max(suffix[i + 1], height[i]);
for(int i = 0; i < height.size(); i++){ //记录每一个位置上的水桶所装的水
if(height[i] < prefix[i] && height[i] < suffix[i])
result += (min(prefix[i], suffix[i]) - height[i]);
}
return result;
}
};双指针法
双指针法需要以前后缀法为基础，实际上是对前后缀法的一种优化，我们可以定义左右指针相向移动，左指针右移的过程中不断更新最大前缀，用一个变量维护即可，右指针左移的过程中同样用一个变量维护最大后缀，我们需要知道这样一条性质：无论是
height[left]
还是
height[right]
，都满足
max_pre >= height[left]
，
max_suf >= height[right]
，这就意味着对于
height[left]
处的柱子来说，只要右侧的最大后缀出现比最大前缀高的情况，就满足了接水的条件，即可开始计算接水量，最坏情况是最大前缀恰好等于
height[left]
，这个时候算出来的接水量为0，当
height[left]
处的柱子接完水后，左指针应当向右移。右边指针也同理，只要出现最大前缀大于最大后缀时，就开始计算
height[right]
处的接水量，最坏情况是接不到水，计算完以后右指针左移。
当左右指针相遇时，
left = right
，注意，此时
height[left]
（或
height[right]
）处仍然有可能接到水，所以这个时候还不能退出循环，注意循环终止条件的设置。
class Solution {
public:
int trap(vector<int>& height) {
int result = 0;
int left = 0;
int right = height.size() - 1;
int max_pre = 0; //记录最大前缀
int max_suf = 0; //记录最大后缀
while(left <= right){
max_pre = max(max_pre, height[left]); //更新最大前缀,保证最大前缀至少>=height[left]
max_suf = max(max_suf, height[right]); //更新最大后缀,保证最大后缀至少>=height[right]
if(max_pre < max_suf){ //最大前缀小于最大后缀
result += (max_pre - height[left]);
left++;
}
else{ //最大前缀大于等于最大后缀
result += (max_suf - height[right]);
right--;
}
}
return result;
}
};