面试题 17.21. 直方图的水量/42. 接雨水

2020-05-16

1.题目描述

直方图的水量

2.题解

对于某一个柱体而言，它上面的水量等于它左右两边柱体最大值最小值的大小减去当前柱体的高度。

3.代码

class Solution { public:int trap(vector<int>& height) {int l=height.size();if (l==0) return 0;vector<int> v1(l,0);vector<int> v2(l,0);v1[0]=height[0];for (int i=1;i<l;i++){v1[i]=max(v1[i-1],height[i]);}v2[l-1]=height[l-1];for (int i=l-2;i>=0;i--){v2[i]=max(v2[i+1],height[i]);}int cnt=0;for (int i=0;i<l;i++){cnt+=min(v1[i],v2[i])-height[i];}return cnt;} };

42

class Solution { public:int trap(vector<int>& height) {int l=height.size();if (l==0) return 0;vector<int> x1(l,0);vector<int> x2(l,0);x1[0]=height[0];for (int i=1;i<l;i++){x1[i]=max(x1[i-1],height[i]);}x2[l-1]=height[l-1];for (int i=l-2;i>=0;i--){x2[i]=max(x2[i+1],height[i]);}int cnt=0;for (int i=0;i<l;i++){cnt+=min(x1[i],x2[i])-height[i];}return cnt;} };

总结

以上是生活随笔为你收集整理的面试题 17.21. 直方图的水量/42. 接雨水的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。