力扣42:接雨水

题目

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

思路

想要解决这道题我们首先要知道一个位置接水量取决于哪些因素，我们可以联想一下现实生活中假如我们使用一个木桶来装水，装水量区决于两个因素，木桶四周最短的那个木板以及木桶底部的高度。因为现实生活中是三维的所以无法定性是哪个方向的木板只能说是四周的木板，但是题目是二维的我们只需要考虑左右两侧就可以了。所以数组中每一个位置的装水量就区决于左右两侧最高的柱子以及当前位置的柱子高度。
那么我们想要解决这道题我们只需要维护两个数组即左侧最高柱子以及右侧最高柱子，注意这个左右两侧是包含当前柱子的高度的，如果左右两侧都没当前柱子高就别提装水这事了。

代码

class Solution {
public:int trap(vector<int>& height) {//每一个位置能存储多少雨水取决于三个条件//1.位置左侧最高的柱子//2.位置右侧最高的柱子//3.位置当前的柱子高度int n = height.size();vector<int> leftheight(n);vector<int> rightheight(n);leftheight[0] = height[0];rightheight[n-1] = height[n-1];for(int i = 1;i < n;i++){//这里的左侧柱子高度是包含当前柱子的高度的。//即[0,i]的范围里最高的柱子，都是闭区间leftheight[i] = max(leftheight[i-1],height[i]);}for(int i = n-2;i >= 0;i--){//[i,n-1]的范围最高的柱子rightheight[i] = max(rightheight[i+1],height[i]);}int res = 0;for(int i = 0;i < n;i++){//也就保证了左侧和右侧最高柱子的最小值起码是等于当前位置不至于接水量为负数res += min(leftheight[i],rightheight[i]) - height[i];}return res;}
};