数组][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;}
};
更多推荐
[数组][dp[]leetcode42:接雨水(hard)
发布评论