[数组][dp[]leetcode42：接雨水(hard)

数组][dp[]leetcode42：接雨水(hard)"/>

[数组][dp[]leetcode42：接雨水(hard)

题目：

题解：

思路：下雨后能达到的最大高度等于两边最大高度的较小值减去当前高度

代码如下：

class Solution {
public://思路：下雨后能达到的最大高度等于两边最大高度的较小值减去当前高度int trap(vector<int>& height) {int n=height.size();//left[i]表示i左边的最大值，right[i]表示i右边的最大值vector<int> left(n),right(n);for(int i=1;i<n;++i){left[i]=max(left[i-1],height[i-1]);}for(int i=n-2;i>=0;--i){right[i]=max(right[i+1],height[i+1]);}int water=0;//第一个和最后一个元素不能接水，因为没有完整的边界//对于下标0<i<n，下标i处能接的雨水量等于两边最大高度的较小值减去当前高度for(int i=1;i<n-1;++i){//下雨后能达到的最大高度等于两边最大高度的较小值减去当前高度int lever=min(left[i],right[i]);water+=max(0,lever-height[i]);}return water;}
};