題目描述
描述：給定一個(gè)直方圖(也稱柱狀圖)，假設(shè)有人從上面源源不斷地倒水，最后直方圖能存多少水量?直方圖的寬度為 1。
上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方圖，在這種情況下，可以接 6 個(gè)單位的水（藍(lán)色部分表示水）。 感謝 Marcos 貢獻(xiàn)此圖。
示例:
輸入: [0,1,0,2,1,0,1,3,2,1,2,1]
輸出: 6
解題思路
思路：最直觀的想法是，當(dāng)前直方圖所能存儲(chǔ)水量等于左邊最大值和右邊最大值之間的最小值減去當(dāng)前高度，直方圖的水量即所有直方圖的水量之和。首先分別前向遍歷、后向遍歷求出當(dāng)前直方圖左邊(包含當(dāng)前)、右邊(包含當(dāng)前)的最大值，然后再前向遍歷求出當(dāng)前直方圖水量即可。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-512557.html
int trap(vector<int>& height)
{
int n=height.size();
//特殊判斷
if(n==0)
return 0;
//存儲(chǔ)當(dāng)前元素左邊(包含當(dāng)前)的最大值
vector<int> left(n,0);
//存儲(chǔ)當(dāng)前元素右邊(包含當(dāng)前)的最大值
vector<int> right(n,0);
left[0]=height[0];
right[n-1]=height[n-1];
for(int i=1;i<n;i++)
left[i]=max(left[i-1],height[i]);
for(int i=n-2;i>=0;i--)
right[i]=max(right[i+1],height[i]);
int res=0;
//所能存儲(chǔ)水量等于左邊最大值和右邊最大值之間的最小值減去當(dāng)前高度
for(int i=0;i<n;i++)
res+=min(left[i],right[i])-height[i];
return res;
}
總結(jié)：注意，之所以包含當(dāng)前，是為了方便計(jì)算，因?yàn)橛锌赡墚?dāng)前就是最高的。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-512557.html
到了這里，關(guān)于【程序員面試金典】面試題 17.21. 直方圖的水量的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
