C++-栅栏蓄水容量

C++-栅栏蓄水容量

瑾兮 发布于 2017-07-17 字数 268 浏览 1069 回复 1

请输入图片描述

有N个靠墙的栅栏,栅栏之间的凹处可以积水,如图中虚线。现在假设不考虑栅栏的宽度,即每个栅栏的宽度为1,栅栏的高度用H[N]表示,请用O(n)的方法,求取栅栏总共蓄水的容量。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

清晨说ぺ晚安 2017-09-23 1 楼

算法思路

首先两端的不可能积水。对于中间的每一个柱(题目称为栅栏)如果柱上能积水,说明这个柱的左边和右边都存在比其高的柱。而这个柱上积水的高度也就是用其左右两边最高的柱中较矮的那个高度-其高度
要在O(n)时间完成。最关键是怎样能够快速计算每一个柱左边和右边最高的高度。

预处理

对数组进行两次遍历分别计算每个柱左边的最高高度maxL[] 和右边的最高高度maxR[]。消耗O(n)
然后按上面的思路再次遍历数组就可以计算总容积Vol。这步消耗O(n)
因此整个算法时间复杂度为O(n),需要O(n)临时空间。

算法代码

int volume(int *d, int n) {
int *maxL = new int[n]; //the max value of d[0](start) -> d[i]
maxL[0] = 0;
int tMax = d[0];
for(int i = 1; i < n; ++i) { //compute the maxL[] .... O(n)
if(d[i] > tMax)
tMax = d[i];
maxL[i] = tMax;
}
int *maxR = new int[n]; //the max value of d[i] -> d[n-1](end)
maxR[n-1] = d[n-1];
tMax = d[n-1];
for(int i = n-2; i >= 0; --i) { //compute the maxR[] .... O(n)
if(d[i] > tMax)
tMax = d[i];
maxR[i] = tMax;
}
int vol = 0;
for(int i = 1; i < n-1; ++i) { //compute Volume .... O(n)
if(maxL[i] > d[i] && maxR[i] > d[i]) {
int lowVal = min(maxL[i], maxR[i]);
vol += lowVal - d[i];
}
}
delete []maxL;
delete []maxR;
return vol; //O(n) in total
}